edited by
320 views
1 votes
1 votes
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?
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
2
Xylene asked Nov 24, 2016
476 views
Can someone construct a PDA for ai bj where i not equal to 3j+1 ? Is it NPDA or DPDA?
1 votes
1 votes
1 answer
3
aditi19 asked Mar 7, 2019
860 views
what is the CFG for the language L=w where number of a’s in w+number of b’s in w=number of c’s in whow to approach this?
0 votes
0 votes
1 answer
4
aditi19 asked Mar 2, 2019
814 views
S->A | BA→ εB->aBbB->bwhat is the complement of the language of this grammar?