0
$\begingroup$

The set of all strings over alphabet a,b not of the form ww for any w. No strings of odd length can be of the form ww . We use the terminal symbols A and B to generate all odd-length strings where the center characters are a and b, respectively.
S -> AB|BA|A|B
A -> aAa|aAb|bAa|bAb|a
B -> aBa|aBb|bBa|bBb|b

To understand why AB and BA are guaranteed to generate strings not of the form ww, understand that A builds an odd-length string, say of length 2k + 1, where k characters precede an a which preceds k more characters. Similarly, B generates a string, say of length 2m + 1, where m a's and b's precede one b preceds m more a's and b's. If we concatenate one to another, we get a string of length 2k + 2m + 2:an even length string-where the middle a of the portion generated by A is k + m + 1 characters away from the central b generated by B. That means that the first k + m + 1 characters cannot be fully replicated in the final k + m + 1 characters.

The first question I have about this proof is that I think they are just intending to generate all the strings of odd length, but there are also strings of even length not in the form ww. Can you explain in an easier way why does that grammar works?

$\endgroup$
  • $\begingroup$ Since $A$ and $B$ both generate strings of odd length, the productions $S\to AB$ and $S\to BA$ generate strings of even length. You have quoted an argument that the even-length strings generated by $AB$ and $BA$ are exactly the ones that are not of the form $ww$. What do you find unclear about this argument? $\endgroup$ – hmakholm left over Monica Mar 4 '17 at 10:15
2
$\begingroup$

Let $L(G)$ be the language which can be derived from the given grammar $G$ $$ S \to AB \mid BA \mid A \mid B \\ A \to aAa \mid aAb \mid bAa \mid bAb \mid a \\ B \to aBa \mid aBb \mid bBa \mid bBb \mid b \\ $$ and the desired language $L$ be $$ L = \Sigma^* \setminus L' \\ \Sigma = \{ a, b \} \\ L' = \{ ww \mid w \in \Sigma^* \} $$ The nonterminals $A$ and $B$ each end up in words of odd length. They seem to derive all possible odd length words from $L$: A rule $$ X \to a X a \mid a X b \mid b X a \mid b X b \mid x $$ grows a word $w$ by one of the four possible steps to grow by two symbols each, and finishes on a central symbol $x$, So $\lvert w \rvert = 2 k + 1$ with $k \in \mathbb{N}_0$.

This leaves the even length words from $L$:

$S$ can turn into $AB$ or $BA$ which gives words $uv$ or $vu$, where $u$ and $v$ are of odd length, note that $u$ and $v$ must not have the same length.

To understand why $AB$ and $BA$ are guaranteed to generate strings not of the form $ww$, understand that $A$ builds an odd-length string, say of length $2k + 1$, where $k$ characters precede an $a$ which preceds $k$ more characters. Similarly, $B$ generates a string, say of length $2m + 1$, where $m$ $a$s and $b$s precede one $b$ preceds $m$ more $a$ and $b$. If we concatenate one to another, we get a string of length $2k + 2m + 2$: an even length string-where the middle $a$ of the portion generated by $A$ is $k + m + 1$ characters away from the central $b$ generated by $B$. That means that the first $k + m + 1$ characters cannot be fully replicated in the final $k + m + 1$ characters.

This explains the application of $S \to AB$, giving a word $$ (a\mid b)^k \, \underbrace{a \, (a \mid b)^k \, (a \mid b)^m}_{1+k+m} b (a \mid b)^m \in \Sigma^{k+1+k+m+1+m} \\ $$ with $k, m \in \mathbb{N}_0$. Comparing this with an equal length string of the form $ww$: $$ \overbrace{x_1 \dotsb x_{k+m+1}}^w \, \overbrace{x_1 \dotsb x_{k+m+1}}^w $$ The requested repetition of $w$ boils down to the condition $$ (ww)_i = x_i = (ww)_{i + k+m+1} \quad (i \in \{1,\dotsc,k+m+1\}) \quad (*) $$ We know the central $a$ of the $A$ production is at position $k+1 \le k+1+m$ thus in the first half, and the central $b$ of the $B$ production is at position $k+1+k+m+1 > k+m+1$, thus in the second half. And that condition $(*)$ is not met, as $$ (ww)_{k+1} = a \ne (ww)_{k+1+k+m+1} = b $$ A similar argumentation will hold for the words derived from $S\to BA$.

What is left open is, if these two productions give all even length words from $L$, $L(G)$ might just be a proper subset of $L$.

$\endgroup$
  • $\begingroup$ .........-> means I got it. $\endgroup$ – daniel Mar 16 '17 at 21:55

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.