3
$\begingroup$

I'm trying to construct a context free grammar for the language $\{a^ib^j:2i\neq3j+1\}$. I found that when $j$ is even, there are no problems. When $j$ is odd, there are some constraints on $i$. Now these are some examples of words that may NOT be parsed by the CFG:

  • aab
  • aaaaabbb (5 a's and 3 b's)
  • aaaaaaaabbbbb (8 a's and 5 b's)
  • ...

But I'm completely stuck on finding a CFG for this language. Are there any tips that might help me in finding CFG's for a more complex language? I'm able to find the CFG for simpler languages, but I find this one particularly hard.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

Try constructing CFGs for the two related languages $$ \{a^ib^j : 2i > 3j + 1\}, \quad \{a^ib^j : 2i < 3j+1\}. $$ This can be accomplished by constructing a grammar for $$ \{a^ib^j : 2i = 3j + 1\} $$ and some related languages.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.