Context free language

Question

Is the language $L=\left \{ (0^{n}1^{n})^{*} |n\geq 0 \right \}$ is DCFL ?

Comments

as i know that DCFL is not closed under kleen closure but here Language is given so we cant use closure property ...

---

closure property works for genral term , but for perticular language dont use it.

Answer 1

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.

Comments

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

---

grammar of DCFL is TYPE 2 grammar. then it must be linear?

---

It's not dcfl . It is violating Dpda definition..

On state A , (A,0,Z) and (A,^,Z) and on state B ,(B,0,Z) and (B,^,Z) violating Dpda definition... please check this

@ Arjun sir

---

Actually most of people don't know regarding this.... unfortunately every time they have mistaken....but your Dpda diagram makes against Dpda definition…

@Arjun sir also agree with this

https://gateoverflow.in/9925/plz-answer

Please see Wikipedia…

Formal definition section

https://en.m.wikipedia.org/wiki/Deterministic_pushdown_automaton