Context Free Grammar (CFG) for Un-Equal numbers of a’s and b’s | CFG for Un-Equal numbers of a’s and b’s

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

L = { w mid text{w has an unequal number of } atext{‘s and } btext{‘s} }

, we need a CFG that generates strings where the number of

a

‘s and

b

‘s are not equal.

We’ll approach this by constructing a CFG that generates strings where:

Here’s a CFG that generates such strings:

$S rightarrow aSb$ :
- This rule adds an $a$ to the beginning and a $b$ to the end, ensuring that the number of $a$ ‘s and $b$ ‘s are not equal by recursively ensuring the mismatch continues in the middle.
$S rightarrow bSa$ :
- This rule adds a $b$ to the beginning and an $a$ to the end, ensuring the same kind of imbalance but starting with more $b$ ‘s than $a$ ‘s.
$S rightarrow aS$ :
- This rule ensures that adding extra $a$ ‘s while the substring $S$ can have any valid imbalance, thus guaranteeing more $a$ ‘s than $b$ ‘s.
$S rightarrow Sb$ :
- This rule ensures that adding extra $b$ ‘s while the substring $S$ can have any valid imbalance, thus guaranteeing more $b$ ‘s than $a$ ‘s.
$S rightarrow a mid b$ :

These rules cover the cases where there is only one $a$ or $b$ , which automatically implies an imbalance.

For the string $aaab$ :
- Start with $S rightarrow aSb$
- To make $S rightarrow aS$ :
  - $S rightarrow a(aSb)b$
  - Continue with $S rightarrow a$ :
    - $S rightarrow a(a(a mid b))b rightarrow aaab$
For the string $b b$ :
- Start with $S rightarrow Sb$ :
  - $S rightarrow b$
- Combining these gives $bb$ .
For the string $aab$
- Start with $S rightarrow aSb$ :
  - $S rightarrow a(a mid b) rightarrow aab$

This CFG effectively generates strings where the number of $a$ ‘s is not equal to the number of $b$ ‘s.

Recent Posts