# Find a grammar for this language

Assume the language: $$L=\left\{w\in\{0,1\}^*\,| \text{ w has odd length and 111 right in the middle}\right\}$$

This is my attempt for constructing a grammar $$G$$ for this language:

$$G: S \rightarrow A111B,\, A \rightarrow 01B |10B|00B|11B,\, B \rightarrow 01A |10A|00A|11A$$

This process adds random even strings of $$\{0,1\}^*$$ to both sides of $$111$$.

However, it must assign $$\varepsilon$$ to $$A$$ and $$B$$ simultaneously, for the even strings to be of equal length and for $$111$$ to stay in the middle of the resulting string.

How can I achieve the last step?

• Your grammar does not generate any string, since no rules have a literal string on the right side. – John L. Nov 15 '18 at 14:18

If you do not want a more complicated (non-context-free) grammar, you cannot coordinate the two steps. The trick is to work the other way around: generate the two "side strings" from one central non-terminal and put the $$111$$ in the end.
• you miss $$111$$,
I propose the grammar $$[ \{0,1\}, \{S\}, R, S]$$ where $$R$$ has the rules $$S\rightarrow 0S0\ |\ 1S1\ |\ 0S1\ |\ 1S0\ |\ 111$$.