HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Grammar for a language: odd length, middle character not repeated

Submitted by: @import:stackexchange-cs··
0
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: 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$$

Context

StackExchange Computer Science Q#7019, answer score: 8

Revisions (0)

No revisions yet.