search
Log In
3 votes
485 views
Is the language $L=\left \{ (0^{n}1^{n})^{*} |n\geq 0 \right \}$ is DCFL ?
in Theory of Computation
retagged by
485 views
0
as i know that DCFL is not closed under kleen closure but here Language is given so we cant use closure property ...
0
closure property works for genral term , but for perticular language dont use it.

1 Answer

6 votes
 
Best answer

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
1
But the grammar which u have written is not linear and we know that every dcfg need to be a linear grammar that is having only one variable in the production.

But u r doing S --> AS which is not allowed in linear grammar.

Also u cannot write a grammar for the above language that is linear.

So the language should be ncfl only not dcfl
0
grammar of DCFL is TYPE 2 grammar. then it must be linear?

Related questions

2 votes
1 answer
1
211 views
1. L = {w | w ∈ {a,b}, na(w) >= nb(w)+1} 2. L = {aibj | i ≠ 2j+1} 3. L = {ambn | m=2n+1} NOTE: 1 - DCFL, 2 - DCFL, 3 -DCFL, but need a proper reason!
asked Sep 19, 2017 in Theory of Computation iarnav 211 views
3 votes
1 answer
3
141 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$ is finite language regular language DCFL not DCFL
asked Nov 10, 2017 in Theory of Computation Prateek Raghuvanshi 141 views
2 votes
2 answers
4
...