3
$\begingroup$

I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language:

$ L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ww\} $ with $ \Sigma = \{a,b\}$

I am trying some rules of the form

$L \Rightarrow a | b $

$S \Rightarrow aSbS\ |\ bSaS\ |\ L\ |\ ab\ |\ ba $

However this is wrong since for example the grammar does not accept 3-symbol strings. I am a little bit stuck with it so any help would be greatly appreciated.

$\endgroup$
1
$\begingroup$

The question has been asked before, but since it's faster to describe the answer than to find the previous question, I'll outline the answer here.

We can characterize words in $L$ as belonging to one of two classes:

  1. Words of odd length.

  2. Words $z_1 \ldots z_n w_1 \ldots w_n$ where $z_i \neq w_i$ for some $i$.

It is easy to generate words of the first type. As for words of the second type, for fixed $i$ and $n$ we can generate them using rules of the form $\Sigma^{i-1} a \Sigma^{n-i} \Sigma^{i-1} b \Sigma^{n-i} = \Sigma^{i-1} a \Sigma^{i-1} \Sigma^{n-i} b \Sigma^{n-i}$ and its counterpart with $a,b$ replaced by $b,a$. I'll let you figure out how to generate all of these words (for all $i,n$).

$\endgroup$
  • 4
    $\begingroup$ "The question has been asked before, but since it's faster to describe the answer than to find the previous question" -- you really have to learn to use the site's search one of these days. ;D Google with site:cs.stackexchange.com is usually quite good. $\endgroup$ – Raphael Feb 9 '16 at 12:20

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