I came across this context-free grammar for the language L = {xy||x|=|y|, x≠y}, but I can't seem to see how it can generate all lengths for x and y. Could someone illustrate this? For example, how would you derive the string "abba" or "aaabbaaa"?

  • $\begingroup$ $S \Rightarrow BA \Rightarrow aBbA \Rightarrow abbA \Rightarrow abba$ $S \Rightarrow BA \Rightarrow aBaA \Rightarrow aaBaaA \Rightarrow aaaBbaaA \Rightarrow aaabbaaA \Rightarrow aaabbaaa$ $\endgroup$
    – Russel
    Commented Mar 3, 2022 at 2:21

1 Answer 1


Suppose that $|x| = |y| = n$ and $x_i \neq y_i$, say $x_i = a$ and $y_i = b$. We can therefore write $x = r a s$ and $y = ubv$, where $|r| = |u| = i-1$ and $|s| = |v| = n-i$. Therefore $$xy = rasubv, $$ where $|r| = i$, $|su| = (n-i) + (i-1)$, $|v| = n-i$. Now let $p$ be the first $i-1$ letters of $su$, and let $q$ be the final $n-i$ letters of $su$, so that $su = pq$. Then $$ xy = rapqbv. $$ Now $A$ generates $rap$ (since $|r| = |p| = i-1$) and $B$ generates $qbv$ (since $|q| = |v| = n-i$), and so the grammar generates $xy$.

Now let's consider your two examples, starting with $abba$. In this case, $x = ab$ and $y = ba$, and so there are two choices for $i$: $i = 1$ and $i = 2$.

If we choose $i = 1$ then $x = ras$ for $r = \epsilon$ and $s = b$, and $y = ubv$ for $u = \epsilon$ and $v = a$. We have $su = b = pq$, and so $p = \epsilon$ and $q = b$. We now generate $xy$ as follows. First, $A \Rightarrow^* rap = a$. Second, $B \Rightarrow^* qbv = bba$. Finally, $S \Rightarrow AB \Rightarrow^* (a)(bba)$.

If we choose $i = 2$ then $x = rbs$ for $r = a$ and $s = \epsilon$, and $y = uav$ for $u = b$ and $v = \epsilon$. We have $su = b = pq$ and so $p = b$ and $q = \epsilon$. We can generate $rbp = abb$ using $B$ and $qav = a$ using $A$, and put them together via $S \Rightarrow BA$ to generate $(abb)(a)$.

In your second example $aaabbaaa$ we similarly have two options for $i$: $i = 1$ and $i = 4$. If we choose $i = 1$ then $x=ras$ for $r = \epsilon$ and $s = aab$, and $y = ubv$ for $u = \epsilon$ and $v = aaa$. Then $su = aab = pq$, and so $p = \epsilon$ and $q = aab$. We generate $rap = a$ using $A$ and $qbv = (aab)b(aaa)$ using $B$, and put them together via $S \Rightarrow AB$ to generate $(a)(aabbaaa)$.

Finally, if $i = 4$ then $x = rbs$ for $r = aaa$ and $s = \epsilon$, and $y = uav$ for $u = baa$ and $v = \epsilon$. Then $su = baa = pq$, and so $p = baa$ and $q = \epsilon$. We generate $rbp = (aaa)b(baa)$ using $B$ and $qav = a$ using $A$, and put them together via $S \Rightarrow BA$ to generate $(aaabbaa)(a)$.


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.