RegularLanguage
Question 1 
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 1 Explanation:
From the given grammar we can draw the DFA,
Question 2 
Language L_{1} is deﬁned by the grammar: S_{1} → aS_{1}bε
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

Question 2 Explanation:
The language L_{1} generated by the grammar contains equal number of a’s and b’s, but b’s comes after a’s.
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.
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 3 
L_{1} and L_{3} only
 
L_{2} only
 
L_{2} and L_{3} only
 
L_{3} only

Question 3 Explanation:
L_{1}: All strings of length 3 or more with same start and end symbol, as everything in middle is consumed by x as per the definition.
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.
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 4 
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 
Question 4 Explanation:
Exp: Σ*  P is the complement of P so it is always regular,
since regular languages are closed under complementation
since regular languages are closed under complementation
Question 5 
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. 
Question 5 Explanation:
If a set is finite then it must be regular , as every language which contains finite elements is regular. Hence, every finite subset of a nonregular set 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.
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 6 
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}^{+}}

Question 6 Explanation:
The regular expression corresponding to option C is:
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.
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 7 
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}

Question 7 Explanation:
Since 3digit prime numbers are finite so language in option A is finite, hence it is regular.
Option B: The DFA contains 6 states
State1: n_{0}(s')  n_{1}(s') = 0
State2: n_{0}(s')  n_{1}(s') = 1
State3: n_{0}(s')  n_{1}(s') = 2
State4: n_{0}(s')  n_{1}(s') = 1
State5: n_{0}(s')  n_{1}(s') = 2
State6: 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.
Option B: The DFA contains 6 states
State1: n_{0}(s')  n_{1}(s') = 0
State2: n_{0}(s')  n_{1}(s') = 1
State3: n_{0}(s')  n_{1}(s') = 2
State4: n_{0}(s')  n_{1}(s') = 1
State5: n_{0}(s')  n_{1}(s') = 2
State6: 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 8 
Both I and IV  
Only I  
Only IV  
Both II and III 
Question 8 Explanation:
Repeat(L) = {www ∈ L} is nonregular language.
Half (L), Suffix (L) and Prefix (L) are regular languages.
Half (L), Suffix (L) and Prefix (L) are regular languages.
Question 9 
(a + b)*  
{ϵ, a, ab, bab}  
(ab)*  
{a^{n}b^{n}  n ≥ 0} 
Question 9 Explanation:
A counter example which proves all the conclusions of the last question in one go should have the following properties:
1) L should be regular due to demand of question.
2) L should be an infinite set of strings.
3) L should have more than one alphabet in its grammar, otherwise repeat(L) would be regular.
∴ (a + b)* is the perfect example to support the conclusions of last questions.
1) L should be regular due to demand of question.
2) L should be an infinite set of strings.
3) L should have more than one alphabet in its grammar, otherwise repeat(L) would be regular.
∴ (a + b)* is the perfect example to support the conclusions of last questions.
Question 10 
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 10 Explanation:
Let regular language L = a*b* and subset of L is a^{n}b^{n}, n ≥ 0, which is not regular. Hence option (B) is false.
Question 11 
Only L1 and L2  
Only L2, L3 and L4  
Only L3 and L4  
Only L3 
Question 11 Explanation:
L1 = {www∈{a,b}*}
⇒ 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.
⇒ 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 12 
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). 
Question 12 Explanation:
Regular languages are closed under,
1) Intersection
2) Union
3) Complement
4) Kleenclosure
Σ*  R_{1} is the complement of R_{1}.
Hence, (B) and (C) are true.
1) Intersection
2) Union
3) Complement
4) Kleenclosure
Σ*  R_{1} is the complement of R_{1}.
Hence, (B) and (C) are true.
Question 13 
Regularity is preserved under the operation of string reversal.
True  
False 
Question 13 Explanation:
Regular language is closed under reversal.
Question 14 
All subsets of regular sets are regular.
True  
False 
Question 14 Explanation:
a*b* is regular but its subset a^{n}b^{n} is not regular.
There are 14 questions to complete.