1
$\begingroup$

(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!

2 Answers 2

1

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.

More detail in the spoiler, but try to get it yourself first.

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).

  • 0
    Thank you for that tip. I was getting to something similar, but your contribution really helped me put it together! :-)2012-10-30
0

The basic rule is S→AABSBCC|ABSC|ASBC|1 where AA, BB and CC 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 0s and 1s to either side (remember that the "middle" 11 is not necessarily actually in the middle, just that the string can be broken into those three bits).

I think there might be a slight problem with this grammar? First of all it doesn't generate string with length 3. Secondly, it generates strings of length 4 like 0010, and I think by problem statement 0010 shall not be in that language? Even if 0110 that has more 1's towards the middle might be an inappropriate string to generate, because it's a length four, and it just does not have a "middle third" with one complete bit (not like two bits sliced in 2/3 and concatenated together shall be valid).

  • 0
    Moreover, I think a length 5 would be okay, like 00100. It's middle third does contain a complete bit undamaged. However a length 5 cannot be generated by the above grammar as well. I'm still trying to find a complete answer.2017-02-14