Regular Languages
Question 1 
Which one of the following is TRUE?
The language L={a^{n} b^{n}│n≥0} is regular.  
The language L={a^{n}│n is prime} is regular.  
The language L={w│w has 3k+1b's for some k∈N with Σ={a,b} } is regular.  
The language L={ww│w∈Σ* with Σ={0,1} } is regular. 
Question 1 Explanation:
The Language L= {a^{n} b^{n}  n>=0} is CFL but not regular, as it requires comparison between a’s and b’s.
L = {a^{n}  n is prime} is CSL, as calculation of “n is prime” can be done by LBA (Turing machine)
L = {ww  w ∈ ∑*} is CSL.
But L = { w  w has 3k+1 b’s for some k ∈ natural number} is regular.
Lets take values of k={1,2,3,….}
So number of b’s will be {4, 7, 10,……….} and number of a’s can be anything.
The DFA will be
L = {a^{n}  n is prime} is CSL, as calculation of “n is prime” can be done by LBA (Turing machine)
L = {ww  w ∈ ∑*} is CSL.
But L = { w  w has 3k+1 b’s for some k ∈ natural number} is regular.
Lets take values of k={1,2,3,….}
So number of b’s will be {4, 7, 10,……….} and number of a’s can be anything.
The DFA will be
Question 2 
Only (I)  
Only (II)  
Both (I) and (II)  
Neither (I) nor (II) 
Question 2 Explanation:
The regular expression equivalent to L_{1} and L_{2} are (a*) and (b*) respectively.
Since L_{1} and L_{2} both are regular languages and regular languages are closed under complementation, so there concatenation (i.e. L_{1}⋅ L_{2}) must also be a regular language.
But,
L_{1}.L_{2} ≠ { a^{n}b^{n}  n ≥ 0}
L_{1}= {ϵ, a ,aa, aaa, aaaa,.............}
L_{2}={ϵ, b, bb, bbb, bbbb, …………}
So L_{1}⋅L_{2} = {ϵ, a ,aa, aaa, aaaa,.............}.{ϵ, b, bb, bbb, bbbb, …………}
L_{1}⋅L_{2}= {ϵ, a, aa, aaa, …………., b, bb, bbb, ……., ab, abb, abbb, …….., aab, aaab, …………..}
Hence L_{1}.L_{2}= { a^{m}b^{n}  m, n ≥ 0}
Since L_{1} and L_{2} both are regular languages and regular languages are closed under complementation, so there concatenation (i.e. L_{1}⋅ L_{2}) must also be a regular language.
But,
L_{1}.L_{2} ≠ { a^{n}b^{n}  n ≥ 0}
L_{1}= {ϵ, a ,aa, aaa, aaaa,.............}
L_{2}={ϵ, b, bb, bbb, bbbb, …………}
So L_{1}⋅L_{2} = {ϵ, a ,aa, aaa, aaaa,.............}.{ϵ, b, bb, bbb, bbbb, …………}
L_{1}⋅L_{2}= {ϵ, a, aa, aaa, …………., b, bb, bbb, ……., ab, abb, abbb, …….., aab, aaab, …………..}
Hence L_{1}.L_{2}= { a^{m}b^{n}  m, n ≥ 0}
Question 3 
Let L_{1} = {w ∈ {0,1}*  w has at least as many occurrences of (110)’s as (011)’s}. Let L_{2} = {w ∈ {0,1}*w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?
L_{1} is regular but not L_{2}  
L_{2} is regular but not L_{1}  
Both L_{1} and L_{2} are regular  
Neither nor L_{1} are L_{2} regular 
Question 3 Explanation:
In L_{1} any string “w” must satisfy the condition:
{Number of occurrences of (110)} ≥ {Number of occurrences of (011)}
Lets analyse the language, consider a string in which occurrence of (110) is more than one.
The following possibilities are: {1100110, 1101110, 110110, ….}
Please observe whenever strings start with “11” then in every situation whatever comes after “11” the string will never violate the condition. So strings of the form 11(0+1)* will always satisfy the condition.
Consider a string in which occurrence of (011) is more than one.
The following possibilities are: {011011, 0111011, 0110011, ….}
In the following possibilities please observe that number of occurrence “011” is two but number of occurrence of (110) is one, which violate the conditions.
If we add “0” in every string mentioned above, i.e. {0110110, 01110110, 01100110, ….} Now, observe that number of occurrence “011” and the number of occurrence of (110) both are equal, which satisfies the conditions.
With these analysis, we can make the DFA , which is mentioned below.
But language L_{2} requires infinite comparison to count the occurrences of (000’s) and (111’s), hence it is not regular.
{Number of occurrences of (110)} ≥ {Number of occurrences of (011)}
Lets analyse the language, consider a string in which occurrence of (110) is more than one.
The following possibilities are: {1100110, 1101110, 110110, ….}
Please observe whenever strings start with “11” then in every situation whatever comes after “11” the string will never violate the condition. So strings of the form 11(0+1)* will always satisfy the condition.
Consider a string in which occurrence of (011) is more than one.
The following possibilities are: {011011, 0111011, 0110011, ….}
In the following possibilities please observe that number of occurrence “011” is two but number of occurrence of (110) is one, which violate the conditions.
If we add “0” in every string mentioned above, i.e. {0110110, 01110110, 01100110, ….} Now, observe that number of occurrence “011” and the number of occurrence of (110) both are equal, which satisfies the conditions.
With these analysis, we can make the DFA , which is mentioned below.
But language L_{2} requires infinite comparison to count the occurrences of (000’s) and (111’s), hence it is not regular.
Question 4 
I and IV only  
I and III only  
I only
 
IV only 
Question 4 Explanation:
Statement I represents a regular language whose regular expression is a* (bb)*. Also it doesn’t require any comparison between “a” and “b” , so it can be recognized by DFA and hence regular.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Question 5 
Which of the following statements about regular languages is NOT true?
Every language has a regular superset  
Every language has a regular subset  
Every subset of a regular language is regular  
Every subset of a finite language is regular

Question 5 Explanation:
Regular languages are not closed under subset.
Question 6 
I only  
I and II  
II and III  
II only 
Question 6 Explanation:
(I) is the correct definition and the other two is wrong because the other two can have any no. of x and y. There is no such restriction over the number of both being equal.
Question 7 
Let Σ = {0,1}, L = Σ* and R = {0^{n}1^{n} such that n >0} then the languages L ∪ R and R are respectively
regular, regular  
not regular, regular  
regular, not regular  
not regular, no regular 
Question 7 Explanation:
L∪R is nothing but L itself. Because R is subset of L and hence regular. R is deterministic context free but not regular as we require a stack to keep the count of 0's to make that of 1's.
There are 7 questions to complete.