Context Free Grammar for {a^mb^mc^n | m , n ε N } | CFG for {a^mb^mc^n

Context Free Grammar for {a^mb^mc^n | m , n ε N } | CFG for {a^mb^mc^n | m , n ε N }

To construct a context-free grammar (CFG) for the language

L = { a^m b^m c^n mid m, n geq 0 }

, where

m

and

n

are non-negative integers, we need a grammar that generates strings with equal numbers of

a

‘s and

b

‘s followed by any number of

c

‘s.

Here’s a CFG for this language:

Start Symbol:

S

Non-terminal Symbols:

S

Terminal Symbols:

a, b, c

Production Rules:

Start Symbol:

S

The production rule $S rightarrow aSb$ ensures that for every $a$ added to the string, a corresponding $b$ is added. This maintains the equality of $a$ ‘s and $b$ ‘s in the string.
The production rule $S rightarrow C$ transitions to handling the $c$ ‘s after all $a$ ‘s and $b$ ‘s are placed.
The non-terminal $C$ generates zero or more $c$ ‘s by the rules $C rightarrow cC$ and $C rightarrow epsilon$ . The rule $C rightarrow cC$ adds $c$ ‘s, while $C rightarrow epsilon$ allows the string to end when there are no more $c$ ‘s to add.