# Finding a Context Free Grammar for this language

(Paraphrasal of problem 2.48a in Sipser - Introduction to the Theory of Computation, 3rd ed.)

The language $L$ consists of all binary strings with a $1$ somewhere in the middle third of the string, and I'm trying to prove $L$ is context-free by showing that it can be generated by a context-free grammar.

Alphabet $A = \{0,1\}$

$L = \{abc \;|\; (a,c \in A^{*}) \wedge (b \in A^{*}1A^{*}) \wedge (|a|=|c|\geq|b|)\}$

So far, I have $S \rightarrow 0S0\; |\; 1S1 \;|\; 0S1 \;|\; 1S0$

This generates $a$ and $c$ AND ensures that $|a| = |c|$. However, I am trying to come up with a way to definitively insert a $1$ at some point, while ensuring that the grammar cannot somehow push that $1$ into $a$ (the first third) or $c$ (the last third).

(I suppose creating a pushdown automaton would also work, and am open to that, as well. However, I usually tend towards CFGs for that kind of question.)

Any advice, pointers, etc. you could offer me will be greatly appreciated - many thanks!

-

You're off to the right start, it just has to be a bit more elaborate, the rough idea is that you want to add a character to $a$ and $c$ for each one you put into $b$, then the last step is to stick the "middle" $1$ in.
The basic rule is $S\rightarrow AABSBCC \;|\; ABSC \;|\; ASBC | 1$ where $A$, $B$ and $C$ got to $0\;|\; 1$, and really only have different labels to highlight the counting. Not that we're not really keeping track of the order, but the step-wise counting ensures we have enough $0$s and $1$s to either side (remember that the "middle" $1$ is not necessarily actually in the middle, just that the string can be broken into those three bits).