CFG for a^i b^j where i != j and i != 2j
The idea is to split the given langauge into to sub languages and then find their union to get the CFG as union of CFG is also a CFG.
So, we consider the following possibilities,
(i) i < j
(ii) j < i < 2j
(iii) i > 2j
and then we find the grammar for each and then find their union to get our grammar.
Let our grammar be, S = S(i) | S(ii) | S(iii)
(i)
S(i) → aS(i)b | Bb
B→ Bb | ε
(ii)
S(ii)→ aCbS(ii) → aCb
C → aCb | D
D→ aaDb | aab
(iii)
S(iii)→ aA
A→ aaAbaA | ε
Get Answers For Free
Most questions answered within 1 hours.