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 
If L_{1} = {a^{n}n≥0} and L_{2} = {b^{n}n≥0}, consider

(I) L_{1}·L_{2} is a regular language
(II) L_{1}·L_{2} = {a^{n}b^{n}n≥0}
Which one of the following is CORRECT?
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 concatenation. So their concatenation (i.e., L_{1}⋅ L_{2}) must also be a regular language.
So, L_{1}⋅L_{2} = { a^{n}b^{n}  n ≥ 0}
Hence, statement (i) is True but statement (ii) is False.
Since L_{1} and L_{2} both are regular languages and regular languages are closed under concatenation. So their concatenation (i.e., L_{1}⋅ L_{2}) must also be a regular language.
So, L_{1}⋅L_{2} = { a^{n}b^{n}  n ≥ 0}
Hence, statement (i) is True but statement (ii) is False.
There are 2 questions to complete.