Let Ln = {0n b n : n ≥ 0} and Lw = {w ∈ {a, b} ∗ : |w| is not a multiple of 10}.
It is clear that Lnis context-free, and Lw is a regular language.
Furthermore, we have L = Ln ∩ Lw, since the intersection of a context-free language and a regular language is context-free, then L is context-free.
So L1 is not regular.
Source : https://raphiinconcordia.files.wordpress.com/2015/05/assgn3-sols.pdf
Second Problem:
L2=complement of {(0n 1n )m│m,n>0}
L4 = {(0n 1n )m│m,n>0}
It is not possible to construct any DFA ,NFA or RE for L4
So L4 is not regular.
Applying Closure property, we say , L2 is not regular.
Second problem Explanation:
Let L = {(0n 1n )│n>0}
We know that L is not regular.
Lc = {(0n 1n )m│m,n>0}
So we can say Lc is closure of L.
As L is not regular, Lc is not regular.
The complement of Lc (L2) is also not regular.
|