retagged by
1,106 views
3 votes
3 votes
Is the language $L=\left \{ (0^{n}1^{n})^{*} |n\geq 0 \right \}$ is DCFL ?
retagged by

1 Answer

Best answer
6 votes
6 votes

Let the language be $L1= \left \{ 0^{N}1^{N} | N\geq 0 \right \}$

For this language, we can design a context free grammar as

$A\rightarrow \epsilon /0A1$

Now, according to the question, $L= L1$*

We can write grammar for this as 

$S\rightarrow \epsilon /AS$

$A\rightarrow \epsilon /0A1$

This grammar generates $\epsilon , A,AA,AAA,AAAA,AAAAA,.................................$

Now, Is this language DCFL or NCFL ? 

We can try to make a DPDA for it. If it exists,,then this language is DCFL.

This language L is DCFL and as well as NCFL.

selected by

Related questions

3 votes
3 votes
1 answer
2
Prateek Raghuvanshi asked Nov 10, 2017
488 views
$L_1 =\{a^n b^m c^n \mid m,n \geq 0\}$ and $L_2=\{ a^n b^n\mid n\geq 0\}$. If $L=L_2-L_1$ then $L$ isfinite languageregular languageDCFL not DCFL
2 votes
2 votes
2 answers
3