99 views
I am trying to construct a CFG for this following langauge: L = $\{0^i 1^j | i \neq j \ and \ i, j > 0\}$, this is what I came up with:

$S \rightarrow A \ | \ B$

$A \rightarrow 0A1 \ |\ A1 \ |\ 011$

$B \rightarrow 0B1 \ |\ 0B \ |\ 001$

Based on the language, we know we can’t have the strings: s = {0,1, 01, 0011 etc}.

And I tested on the following strings that we can have: s = {011, 00111, 001, 00011, ...} and it worked.

So, my question is, is this correct CFG for this particular L?

yes, it's correct.
Ah ok, thank you for clearing my doubts.