Consider the language below, on the alphabet $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y \mid x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$

I need to define a CFG for this language. I've tried couple of CFGs but they all failed in one way or another.

I'd be glad for help.

  • 3
    $\begingroup$ Could you show us what you have tried? $\endgroup$
    – Jake
    May 2, 2015 at 16:39
  • 2
    $\begingroup$ What have you tried? ...Try to simplify your problem. Start with only $a$ and $\$$. That should be easier. Then modify your solution to add the $b$. Why do I say that? Because only length matters, not the difference between $a$ and $b$. So I am taking advantage of it. Many problems are quite simple if you stop to analyze what matters and what does not. $\endgroup$
    – babou
    May 2, 2015 at 17:03
  • $\begingroup$ I'm sure this was asked before on this site. Did you try to look it up? $\endgroup$
    – Ran G.
    May 12, 2015 at 1:05

1 Answer 1


Hint: $$ L = \{ \Sigma^{m+1} \Sigma^n \$ \Sigma^n : n,m \geq 0 \} \cup \{ \Sigma^n \$ \Sigma^n \Sigma^{m+1} \}, $$ where $\Sigma = \{a,b\}$.


Your Answer

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

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