patternMinor
Grammar for a language: odd length, middle character not repeated
Viewed 0 times
repeatedlengthcharacterlanguagegrammarformiddlenotodd
Problem
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:
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
Can someone help with a grammar for $L$?
$$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$?
Solution
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$$
$$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$$
Context
StackExchange Computer Science Q#7019, answer score: 8
Revisions (0)
No revisions yet.