3
$\begingroup$

Consider the following language over the alphabet $\mathcal{A} = \{a,b,c\}$: $$L = \left\{w \in \mathcal{A}^* \mid \text{\(|w|\) is odd and the middle character in \(w\) occurs nowhere else in \(w\)} \right\}$$

I am trying to come up with a grammar for $L$, but I'm getting nowhere. I came up with some sample strings from the language which would be accepted: b, abcab, accbcaa I understand the length of the string has to be odd, and the middle character cannot be repeated anywhere in the string.

Therefore, the above three strings are accepted. However, something like aabbb will not accepted, because even though the length is odd, the middle character is repeated.

Can someone help with a grammar for $L$?

$\endgroup$
8
$\begingroup$

Assume the middle character is $a$. Then a grammar is $$A \rightarrow bAb | bAc | cAb | cAc | a$$ Similarly, we can define nonterminals $B$ and $C$ for the strings in our language where $b$ and $c$, respectively, are the middle symbols. Given those, you can get a grammar for your language by taking the union: $$S \rightarrow A | B | C$$

$\endgroup$

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.