Contex free grammar

counter · **Joined:** Wed, 1 Jun 2011 23:21:54 UTC **Posts:** 2

Construct Contex free grammar that recognize the language :
$L= { a^{n} b^{m} c^{2k} | m = 2n , k >= 1 }$
Can someone help me

outermeasure · **Posted:** Thu, 2 Jun 2011 08:21:12 UTC

counter wrote:

Construct Contex free grammar that recognize the language :
$L= { a^{n} b^{m} c^{2k} | m = 2n , k >= 1 }$
Can someone help me

Can you construct a rule for a^n b^m

? Now stick the $c^{2k}$ at the end.

counter · **Joined:** Wed, 1 Jun 2011 23:21:54 UTC **Posts:** 2

Something like this - > ${a^{n}b^{2n}|| S -> E , S -> aSb^{2}} ////{c^{2k}|k >= 1}$

outermeasure · **Posted:** Thu, 2 Jun 2011 09:37:04 UTC

counter wrote:

Something like this - > ${a^{n}b^{2n}|| S -> E , S -> aSb^{2}} ////{c^{2k}|k >= 1}$

That isn't exactly what we want.

OK, so $S\to aSb^2\mid\epsilon$ generates all a^nb^m

that we want. Unfortunately that isn't the whole story, so we can't really use the letter S. Switch that to T, say: $T\to aTb^2\mid \epsilon$

Now can you cook up a rule for $c^{2k}, k\geqslant 1$ ? Say that is the language

.

Finally, glue these pieces together, which forms the entire language we want: $S\to TU$ .

So the end result is three rules: one for how to get T, one for how to get U, and one rule for S.

(By the way, it is context-free grammar)

S.O.S. Mathematics CyberBoard

Contex free grammar

Who is online