Context Free Grammar (CFG) for Even String ((a+b)(a+b))* | CFG for Even String ((a+b)(a+b))*

L= { ε, aa , bb , ab , ba, ………………………..}

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

{w mid w text{ is an even-length string over } {a, b}}

, we need a CFG that generates strings where the total length of the string is even. The language described can be expressed as

(a+b)(a+b)^*

, which represents strings of even length over the alphabet

{a, b}

CFG for Even-Length Strings

Here’s a CFG that generates all strings of even length over the alphabet

{a, b}

1.Start Symbol: S

2.Production Rules:

Explanation of the Rules:

1. :

This rule ensures that the string generated has an even length by generating two symbols at a time. The non-terminal $A$ generates a single character (either $a$ or $b$ ), and $S$ generates two such characters, ensuring that the total length is always even.

2. :

These rules generate individual characters $a$ or $b$ , which are used by $S$ to create strings of even length.

Example Derivations:

For the string $ab$ :

For the string $aabb$ :

$S Rightarrow AA$
Applying $A rightarrow a$ and $A rightarrow b$ :
- First pair: $A rightarrow a$ and $A rightarrow a$ gives $a a.$
- Second pair: $A rightarrow b$ and $A rightarrow b$ gives $bb$ .
Combining these, we get: $aabb$ .

For the string $abab$ :

This CFG ensures that all generated strings are of even length by using the production

S rightarrow AA

to pair up characters, guaranteeing that the total length of the string is always even.

Recent Posts