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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+3 votes

+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.

+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

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.6k
- Others 1.8k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,339 questions

55,765 answers

192,354 comments

90,815 users