Regular Languages
Question 1 |
Which one of the following is TRUE?
The language L={an bn│n≥0} is regular. | |
The language L={an│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= {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
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 |
If L1 = {an|n≥0} and L2 = {bn|n≥0}, consider
-
(I) L1·L2 is a regular language
(II) L1·L2 = {anbn|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 L1 and L2 are a* and b* respectively.
Since L1 and L2 both are regular languages and regular languages are closed under concatenation. So their concatenation (i.e., L1⋅ L2) must also be a regular language.
So, L1⋅L2 = { anbn | n ≥ 0}
Hence, statement (i) is True but statement (ii) is False.
Since L1 and L2 both are regular languages and regular languages are closed under concatenation. So their concatenation (i.e., L1⋅ L2) must also be a regular language.
So, L1⋅L2 = { anbn | n ≥ 0}
Hence, statement (i) is True but statement (ii) is False.
There are 2 questions to complete.