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$ – 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.

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$ – Andrew Nov 15 '18 at 14:34

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.