636 views
2 votes
2 votes

Consider the following languages:
L1={an bn:n≥0 and n is not multiple of 5}
L2=complement of {(0n 1n )m│m,n>0}

1 Answer

0 votes
0 votes

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, Lis not regular. 
The complement of  Lc  (L2) is also not regular.

edited by

Related questions

2 votes
2 votes
1 answer
1
VS asked Jan 24, 2018
588 views
L={ xy | x,y$\epsilon$ (a+b)*, na(x) = nb(y) }
1 votes
1 votes
0 answers
2
gari asked Jan 1, 2018
630 views
Identify the language. apbqcrds | p+r=q+s
1 votes
1 votes
0 answers
4
set2018 asked Dec 8, 2017
365 views
Let L = {ambnbkdl⎪(n+k = odd) only if m = l; m, n, k, l 0}. Which of the following is true about L?1)L is CFL but not DCFL2)L is regular but not CFL3)L is DCFL but not...