CFG for strings with unequal numbers of a and b – Context-free grammar.

CFG for strings with unequal numbers of a and b – Context-free grammar.

CFG for strings with unequal numbers of a and b

S->aY|bX
X->b|bS|aYY|epsilon
Y->a|aS|bXX|epsilon

How to read abb?

S->aY

->abXX

->ab.epsilon.epsilon

->ab

How to read aab?

S->aY

->aaS

->aabX

->aab.epsilon

->aab

 

CFG for strings with unequal numbers of 0 and 1

S->0Y|1X
A->1|1S|1YY|epsilon
Y->0|0S|0XX|epsilon