Find a Context-Free Grammar for this Context-Free Language

66 Views Asked by At

$$ L = \{w_1w_2 : w_1, w_2\, \in \, \{a,b\}^*, w_1 \ne w_2\} $$ So far I have produced this grammar which will produce a string of odd length which follows that $w_1$ and $w_2$ wouldn't be equal. $$ S \to aSa\,|\,aSb\,|\,bSa\,|\,bSb\,|\,a\,|\,b $$

1

There are 1 best solutions below

0
On BEST ANSWER

Note that $L=\{a,b\}^*\setminus\{\epsilon\}$. Hence $$S\to aS|bS|a|b $$ should do it.