RegularLanguage
Question 1 
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
Suffix (L) = {y ∈ Σ* such that xy ∈ L}  
{ww^{R} │w ∈ L}  
Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}  
L ∙ L^{R} = {xy │ x ∈ L, y^{R} ∈ L} 
Question 2 
For Σ = {a,b}, let us consider the regular language L = {xx = a^{2+3k} or x = b^{10+12k}, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
3  
9  
5  
24 
For any language L, there exists an integer n, such that for all x ∈ L with x ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) uv ≤ n
(2) v ≥ 1
(3) for all i ≥ 0: uv^{i}w ∈ L
We have to find "n" which satisfies for all the strings in L.
Considering strings derived by b^{10+12k}.
The minimum string in L = "bbbbbbbbbb" but this string b^{10} cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts "uvw" must be greater than 10.
Question 3 
Which of the following languages is generated by the given grammar?
{a^{n}b^{m} n,m ≥ 0}  
{w ∈ {a,b}*  w has equal number of a’s and b’s}  
{a^{n} n ≥ 0}∪{b^{n} n ≥ 0}∪{a^{n} b(sup>nn ≥ 0}  
{a,b}* 
Question 4 
Language L_{2} is deﬁned by the grammar: S_{2} → abS_{2}ε
Consider the following statements:
P: L_{1}is regular
Q: L_{2}is regular
Which one of the following is TRUE?
Both P and Q are true  
P is true and Q is false  
P is false and Q is true  
Both P and Q are false

So, in order to compare equality between a’s and b’s memory (stack) is required.
Hence, L_{1} is not regular.
Moreover, L_{1} = {a^{n} b^{n}  n ≥ 0} which is DCFL.
The language L_{2} generated by grammar contains repetition of “ab” i.e. L_{2} = (ab)* which is clearly a regular language.
Question 5 
Which of the following language is/are regular ?
 L1: {wxw^{R} ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} w^{R} is the reverse of string w
L2: {a^{n}b^{m} ⎪m ≠ n and m, n≥0}
L3: {a^{p}b^{q}c^{r} ⎪ p, q, r ≥ 0}
L_{1} and L_{3} only  
L_{2} only  
L_{2} and L_{3} only  
L_{3} only 
L_{2}: In this number of a's is dependent on number of b's. So PDA is needed.
L_{3}: Any number of a's followed by any number of b's followed by any number of c's. Hence Regular.
Question 6 
Let P be a regular language and Q be a contextfree language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be [p^{n}q^{n}  n ∈ N]). Then which of the following is ALWAYS regular?
P ∩ Q  
P – Q  
Σ* – P  
Σ* – Q 
since regular languages are closed under complementation.
Question 7 
Which of the following is TRUE?
Every subset of a regular set is regular.  
Every finite subset of a nonregular set is regular.  
The union of two nonregular sets is not regular.
 
Infinite union of finite sets is regular. 
Every subset of regular set is regular, is false. For example L = {an bn  n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two nonregular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {a^{n} b^{n}  n ≥ 0} and its complement L^{c} = {a^{m} b^{n}  m ≠ n } U b*a*.
If we take UNION of L and L^{c} , we will get ∑*, which is regular. Hence the UNION of two nonregular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.
Question 8 
Which of the following languages is regular?
{ww^{R}w ∈ {0,1}^{+}}  
{ww^{R}xx, w ∈ {0,1}^{+}}  
{wxw^{R}x, w ∈ {0,1}^{+}}  
{xww^{R}x, w ∈ {0,1}^{+}} 
0 (0+1)^{+} 0 + 1 (0+1)^{+} 1
Any string which begins and ends with same symbol, can be written in form of “wxw^{r}”
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and w^{r} = 1.
Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxw^{r}” and L = {wxw^{r}  x,w ϵ {0,1}^{+}} is a regular language.
Question 9 
If s is a string over (0 + 1)* then let n_{0}(s) denote the number of 0’s in s and n_{1}(s) the number of 1’s in s. Which one of the following languages is not regular?
L = {s ∈ (0+1)*  n_{0}(s) is a 3digit prime}  
L = {s ∈ (0+1)*  for every prefix s' of s,n_{0}(s')  n_{1}(s') ≤ 2}  
L = {s ∈ (0+1)* n_{0}(s)  n_{1}(s) ≤ 4}
 
L = {s ∈ (0+1)*  n_{0}(s) mod 7 = n_{1}(s) mod 5 = 0}

Option B: The DFA contains 6 states
State 1: n_{0}(s')  n_{1}(s') = 0
State 2: n_{0}(s')  n_{1}(s') = 1
State 3: n_{0}(s')  n_{1}(s') = 2
State 4: n_{0}(s')  n_{1}(s') = 1
State 5: n_{0}(s')  n_{1}(s') = 2
State 6: Dead state (trap state)
Hence it is regular.
Option D: Product automata concept is used to construct the DFA.
mod 7 has remainders {0,1,2,3,4,5,6} and mod 5 remainders {0,1,2,3,4}
So product automata will have 35 states.
But option C has infinite comparisons between number of 0’s and 1’s.
For ex: n_{0}(s) = 5 and n_{1}(s) = 1 then n_{0}(s)  n_{1}(s) = 4 and if n_{0}(s) = 15 and n_{1}(s) = 11 then n_{0}(s)  n_{1}(s) = 4.
Hence this is CFL.
Question 10 
Consider the following languages:
 L1 = {www ∈ {a,b}*}
L2 = {ww^{R}w ∈ {a,b}*, w^{R} is the reverse of w}
L3 = {0^{2i}i is an integer}
L3 = {0^{i2}i is an integer}
Which of the languages are regular?
Only L1 and L2  
Only L2, L3 and L4  
Only L3 and L4  
Only L3 
⇒ This is not regular language. We can't be able to identify where the 'w' will ends and where the next 'w' starts.
L2 = {ww^{R}w∈{a,b}*, w^{R} is the reverse of w}
⇒ This also not a regular language. We can't identify where 'w' ends.
L4 = {0^{i2}i is an integer}
= {0^{i}*0^{i}i is an integer}
⇒ This is also not a regular language. We can't identify where 0^{i} ends.
L3 = {0^{2i}i is an integer}
⇒ This is regular. We can easily find whether a string is even or not.
Question 11 
(a) Given that A is regular and A∪B is regular, does it follow that B is necessarily regular? Justify your answer.
(b) Given two finite automata M1, M2, outline an algorithm to decide if L(M1)⊆L(M2). (note: strict subset)
Theory Explanation. 
Question 12 
Which of the following statements is false?
Every finite subset of a nonregular set is regular  
Every subset of a regular set is regular  
Every finite subset of a regular set is regular  
The intersection of two regular sets is regular 
Question 13 
Consider the following statements.
 I. If L_{1} ∪ L_{2} is regular, then both L_{1} and L_{2} must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?
Both I and II
 
II only  
Neither I nor II  
I only

Assume L_{1} = {a^{n} b^{n}  n>0} and L_{2} = complement of L_{1}
L_{1} and L_{2} both are DCFL but not regular, but L_{1} U L_{2} = (a+b)* which is regular.
Hence even though L_{1} U L_{2} is regular, L_{1} and L_{2} need not be always regular.
Statement II is wrong.
Assume the following finite (hence regular) languages.
L_{1} = {ab}
L_{2} = {aabb}
L_{3} = {aaabbb}
.
.
.
L_{100} = {a^{100} b^{100}}
.
.
.
If we take infinite union of all above languages i.e,
{L_{1} U L_{2} U ……….L_{100} U ……}
then we will get a new language L = {a^{n} b^{n}  n>0}, which is not regular.
Hence regular languages are not closed under infinite UNION.
Question 14 
Choose the correct alternatives (More than one may be correct). Let R_{1} and R_{2} be regular sets defined over the alphabet Σ Then:
R_{1} ∩ R_{2} is not regular.  
R_{1} ∪ R_{2} is regular.  
Σ* − R_{1} is regular.  
R_{1}* is not regular.  
Both (B) and (C). 
1) Intersection
2) Union
3) Complement
4) Kleenclosure
Σ*  R_{1} is the complement of R_{1}.
Hence, (B) and (C) are true.
Question 15 
Regularity is preserved under the operation of string reversal.
True  
False 