CODEWITHSUNDEEP
regexcontext-free-grammarfinite-automatacontext-free-languagechomsky-normal-form
Ejaz Ahamed
Ejaz Ahamed

Reputation: 31

Context free grammar for CFL

enter code hereHallo, this is my question

Give context free grammar for CFL L = {a^nb^mc^n | m, n ∈ N0}

My answer is S-> ASC| B A-> aA| a B-> bB| b C-> cC| c

Whether my answer or not ? I am not sure about it. Need some help. thanks in advance

Upvotes: 0

Views: 610

Answers (1)

Peter Leupold
Peter Leupold

Reputation: 1212

Your grammar generates the language

L = {a^n b^m c^k | m, n, k ∈ N0}

because the numbers of times that the rules A->aA and C->cC are applied are independent. If you want n=k, then you have to generate the a and c in the same rule. For example like this:

S -> aSc | B .

In a second phase you generate an arbitrary number of b in the middle:

B -> bB | <empty string> .

Upvotes: 3

Related Questions