412 views
0 votes
0 votes

Is it possible to give a context-free grammar for the language below :

L = { anbmcndm | n, m >=1 }

As, my analysis,whenever we try to produce equal a and c and try to put b in between, it would not be possible for us to put d just next to the stream of c's.

hence,  it is not possible to give a Context Free Grammar for this language.

Is my analysis correct?

2 Answers

0 votes
0 votes
Push a's to stack. If you want to compare it with c's then you have to ignore b's.
If you will ignore b's then what to compare with 'd' ?
Simple. Hence its not context free.

Related questions

0 votes
0 votes
1 answer
1
Ayush Upadhyaya asked Mar 20, 2017
527 views
For the language L = { anbmcmdn : n , m>=1 }I came with following set of productions :S >aSd | AA bAc | bcwhereas the answer was given as belowS aSd | aAdA bAc | bcho...
0 votes
0 votes
1 answer
2
Sahil1994 asked Nov 30, 2017
305 views
HI Mates, Is it true or false..? If yes or no please explain..?Every Regular set has a LR(1) Grammar....?
13 votes
13 votes
2 answers
3
Prajwal Bhat asked Jan 15, 2017
5,185 views
1. LL(k) grammars have one to one correspondance with DCFL's2. LR(k) grammars have one to one correspondance with CFL'sWhich of them is True and explain it bit clearly?
0 votes
0 votes
2 answers
4
junaid ahmad asked Jul 22, 2018
763 views
Please provide example to disapprove the following points:-1.every DCFG need not be a LR(K).2.every DCFG need not be a LL(K).3.every DCFL is not LL(k).