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 '15 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 '15 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 '15 at 1:05

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, privacy policy and cookie policy

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