edited by
2,788 views
3 votes
3 votes

$L = \{ 0^{n+m }1^{n+m} 0^m \mid n, m \geq 0 \}$

The above language is 

(a) CFL but not Regular

(b) CSL but not CFL

(c) RE but not CSL

(d) None of the above

I thought the answer would be (b) CSL but not CFL but it was given as (c) RE but not CSL
Can anyone explain how?

edited by

1 Answer

Best answer
11 votes
11 votes

L = { 0n+m 1n+m 0m | n, m >= 0 } 
push all (m+n) os first...now pop all of them for (m+n) 1s..now ur stack doesnt contain anything to match with m 0s coming next..so it is not CFL...if u can somehow look back or inshort have a queue..it is possible to keep the count..hence it is CSL so RE also..

selected by

Related questions

17 votes
17 votes
4 answers
1
gatecse asked Aug 20, 2014
5,665 views
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$$L$ is RE but $L'$ is not REBoth $L$ and $L'$ are RE$L$ is not RE but $L'$ is REBoth $L$ and $L'$ are not RE
2 votes
2 votes
1 answer
3
Anurag_s asked Aug 15, 2015
1,962 views
Answer True/False for the statements:S1: $L ≤_m \{0^n1^n \mid n ≥ 0\}$ then $L$ is decidable.S2: if $L$ is R.E. and $L’ ⊆ L$ then $L’$ is recursively enumerable...
1 votes
1 votes
2 answers
4
kvkumar asked Dec 3, 2016
641 views
L = {an bam|n,m ≥ 0 and n = m mod 5} is regular