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?

  • $\begingroup$ Your grammar does not generate any string, since no rules have a literal string on the right side. $\endgroup$ – Apass.Jack 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.

Further problems with your grammar are:

  • you miss $111$,
  • since your intention is to generate 2 symbols both at the front and at the end, you would add 4 instead of 2 and thus miss every second odd number.

I propose the grammar $$[ \{0,1\}, \{S\}, R, S]$$ where $R$ has the rules $S\rightarrow 0S0\ |\ 1S1\ |\ 0S1\ |\ 1S0\ |\ 111$.

  • $\begingroup$ Thanks, it's so much easier this way! $\endgroup$ – Jevaut Nov 15 '18 at 14:34

Your Answer

