in Theory of Computation edited by
313 views
1 vote
1 vote
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?
in Theory of Computation edited by
313 views

2 Comments

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

Please log in or register to answer this question.

Related questions