Regular language
Question 1 
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 1 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 2 
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 2 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 3 
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 3 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 4 
Both I and IV  
Only I  
Only IV  
Both II and III 
Question 4 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 5 
(a + b)*  
{ϵ, a, ab, bab}  
(ab)*  
{a^{n}b^{n}  n ≥ 0} 
Question 5 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 6 
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 6 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 7 
Only L1 and L2  
Only L2, L3 and L4  
Only L3 and L4  
Only L3 
Question 7 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 8 
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 8 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 9 
Regularity is preserved under the operation of string reversal.
True  
False 
Question 9 Explanation:
Regular language is closed under reversal.
Question 10 
All subsets of regular sets are regular.
True  
False 
Question 10 Explanation:
a*b* is regular but its subset a^{n}b^{n} is not regular.
There are 10 questions to complete.