I have been trying to create a CFG for the set $\{w=a^iba^j \mid i \neq j\}$.

To my understanding, there are essentially 2 scenarios, one where there are more $a$s on the left side of $b$, and one where there are more $a$s on the right side of $b$. So far I have come up with: \begin{align} S &= TbR \mid RbT \\ T &= aT \mid \varepsilon \\ R &= TaT \end{align} My intention is the have $R$ to always have more $a$s than $T$, however I don't think this is correct as $T$ can be greater than $R$ in this definition, as $R$ could take be just $a$ while $T$ is $aa$.

I need a bit of help defining 2 variables $T$ and $R$, where $R$ always has more $a$s than $T$.


Equal numbers of a’s on either side, then the middle is replaced by a+b or by ba+.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your help! If anyone anyone was wondering for the final solution, I ended up with: S=Tb|bT|aSa, T=aT|a $\endgroup$ – DoubleRainbowZ Oct 12 '19 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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