I am doing an exercise from Models Of Computation - Ch - 5, Q-1(r).

Design a grammar that generates this context-free language

$\{ x\space\$\space y^R \,|\, x, y \in\{0, 1\}^* \text{ and } x \ne y\}$

Any hint will be nice.

(My try: I can't seem to come up with a grammar. The pushdown automaton that can accept this language seems easy though. First push all of x into the stack, which can be identified on seeing the $. Keep matching y's characters one by one with top of stack character and pop until the first mismatch. If no mismatch is encountered and the stack is empty as well as y is exhausted, then reject. If a mismatch is encountered, or if the stack becomes empty before y is exhausted, or y is exhausted and stack is still not empty, then accept.)

  • 1
    $\begingroup$ 1. If you can come up with a pushdown automaton, you should be essentially done. Any decent textbook will describe how to convert a PDA to a context-free grammar, so just apply that algorithm by hand. 2. See also cs.stackexchange.com/q/307/755 $\endgroup$
    – D.W.
    Mar 22, 2016 at 0:26

2 Answers 2


Hint: Break this into four different cases:

  1. Words of the form $x\$y$ where $|x|>|y|$.
  2. Words of the form $x\$y$ where $|x|<|y|$.
  3. Words of the form $\Sigma^* 0 \Sigma^n \$ \Sigma^n 1 \Sigma^*$.
  4. Words of the form $\Sigma^* 1 \Sigma^n \$ \Sigma^n 0 \Sigma^*$.
  • $\begingroup$ Aha. I have translated your cases into a grammar, which I am fairly certain is correct. (EBNF currently, converting to proper BNF is pretty mechanical) Thanks. $\endgroup$
    – slnsoumik
    Mar 21, 2016 at 23:34
  • 1
    $\begingroup$ @soumik Don't forget to prove your claim. $\endgroup$
    – Raphael
    Mar 22, 2016 at 2:05

Since I have been told to somehow prove that the grammar indeed generates the language describe, I am adding that in the form of an answer.

Breaking the language into 6 subsets (not mutually exclusive) and giving rules for generating each. The first two cases generate all those words such that $|x| \ne |y|$

  • Case 1: $|x| > |y|$

    $\begin{align*} X_{Longer} &\to (0 \mid 1) \space X_{Longer} \space (0 \mid 1) \\ X_{Longer} &\to (0 \mid 1)^+ \space \$ \end{align*}$

  • Case 2: $|x| < |y|$

    $\begin{align*} Y_{Longer} &\to (0 \mid 1) \space Y_{Longer} \space (0 \mid 1) \\ Y_{Longer} &\to \$\space(0 \mid 1)^+ \end{align*}$

The next 4 cases generate words where the first mismatch occurs at the $(|x| - n + 1)$-th character of string $x$ and $n$-th character of string $y$ for all $n > 0$. (Note, $(|x| - n + 1)$-th character of string $x$ is the same as saying $n$-th character of $x^R$)

The rules have names of the form $M_{c, l, r}$ where $c$ is the character which repeats consecutively $n$ times toward the front and back of the $\$$ before the mismatch. $l$ and $r$ are the mismatching characters in $x$ and $y$ respectively.

  • Case 3: Words of the form $(0\mid1)^*\space 0 \space 1^n\space\$ \space 1^n \space 1 \space (0\mid1)^*, \forall n \geq 0$

    $M_{1, 0, 1} \to (0\mid1)^*\space 0 \space O \space 1 \space (0\mid1)^*$

  • Case 4: Words of the form $(0\mid1)^*\space 1 \space 1^n\space\$ \space 1^n \space 0 \space (0\mid1)^*, \forall n \geq 0$

    $M_{1, 1, 0} \to (0\mid1)^*\space 1 \space O \space 0 \space (0\mid1)^*$

  • Case 5: Words of the form $(0\mid1)^*\space 0 \space 0^n\space\$ \space 0^n \space 1 \space (0\mid1)^*, \forall n \geq 0$

    $M_{0, 0, 1} \to (0\mid1)^*\space 0 \space Z \space 1 \space (0\mid1)^*$

  • Case 6: Words of the form $(0\mid1)^*\space 1 \space 0^n\space\$ \space 0^n \space 0 \space (0\mid1)^*, \forall n \geq 0$

    $M_{0, 1, 0} \to (0\mid1)^*\space 1 \space Z \space 0 \space (0\mid1)^*$

And to complete, there's the $O$ and $Z$ rules

$\begin{align*} O &\to 1\space O \space 1 \\ O &\to \$ \\ Z &\to 0\space Z \space 0\\ Z &\to \$ \end{align*}$

So the starting non-terminal is:

$S \to X_{Longer} \mid Y_{Longer} \mid M_{1, 0, 1} \mid M_{1, 1, 0} \mid M_{0, 1, 0} \mid M_{0, 0, 1}$

  • $\begingroup$ a) In TCS, EBNF is not usually used. So if you wanted to hand your grammar in, you might need to unfold these alternatives. b) The grammar looks okay to me, if maybe a bit more complicated than necessary (owing to the subset construction). c) There is no proof here. $\endgroup$
    – Raphael
    Mar 22, 2016 at 8:12
  • $\begingroup$ Regarding point(B), yes I basically split the last two cases by @Yuval Filmas into four because I found it a bit easier to imagine, if that's what you are referring to. Regarding your point (C), I will study your technique and try to apply it and maybe update this answer. Thank you. $\endgroup$
    – slnsoumik
    Mar 22, 2016 at 9:11

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.