Regular Languages

Question 1
Which one of the following is TRUE?
A
The language L={an bn│n≥0} is regular.
B
The language L={an│n is prime} is regular.
C
The language L={w│w has 3k+1b's for some k∈N with Σ={a,b} } is regular.
D
The language L={ww│w∈Σ* with Σ={0,1} } is regular.
       Theory-of-Computation       Regular Languages       GATE 2014(Set-01)
Question 1 Explanation: 
The Language L= {an bn | n>=0} is CFL but not regular, as it requires comparison between a’s and b’s.
L = {an | 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
A
Only (I)
B
Only (II)
C
Both (I) and (II)
D
Neither (I) nor (II)
       Theory-of-Computation       Regular Languages       Gate 2014 Set -02
Question 2 Explanation: 
The regular expression equivalent to L1 and L2 are (a*) and (b*) respectively.
Since L1 and L2 both are regular languages and regular languages are closed under complementation, so there concatenation (i.e. L1⋅ L2) must also be a regular language.
But,
L1.L2 ≠ { anbn | n ≥ 0}
L1= {ϵ, a ,aa, aaa, aaaa,.............}
L2={ϵ, b, bb, bbb, bbbb, …………}
So L1⋅L2 = {ϵ, a ,aa, aaa, aaaa,.............}.{ϵ, b, bb, bbb, bbbb, …………}
L1⋅L2= {ϵ, a, aa, aaa, …………., b, bb, bbb, ……., ab, abb, abbb, …….., aab, aaab, …………..}
Hence L1.L2= { ambn | m, n ≥ 0}
Question 3
Let L1 = {w ∈ {0,1}* | w has at least as many occurrences of (110)’s as (011)’s}.  Let L2 = {w ∈ {0,1}*|w  has at least as many occurrences of (000)’s as (111)’s}.  Which one of the following is TRUE?
A
L1 is regular but not L2
B
L2 is regular but not L1
C
Both L1 and L2 are regular
D
Neither nor L1 are L2 regular
       Theory-of-Computation       Regular languages       Gate 2014 Set -02
Question 3 Explanation: 
In L1 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 L2 requires infinite comparison to count the occurrences of (000’s) and (111’s), hence it is not regular.
Question 4
 
A
I and IV only
B
I and III only
C
I only
D
IV only
       Theory-of-Computation       Regular Languages       Gate-2008
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)*.
Question 5
Which of the following statements about regular languages is NOT true?
A
Every language has a regular superset
B
Every language has a regular subset
C
Every subset of a regular language is regular
D
Every subset of a finite language is regular
       Theory-of-Computation       Regular Languages       Gate 2006-IT
Question 5 Explanation: 
Regular languages are not closed under subset.
Question 6
 
A
I only
B
I and II
C
II and III
D
II only
       Theory-of-Computation       Regular Languages       Gate-1995
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 = {0n1n such that n >0} then the languages L ∪ R and R are respectively
A
regular, regular
B
not regular, regular
C
regular, not regular
D
not regular, no regular
       Theory-of-Computation       regular Languages       Gate-1995
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.