Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Thank you for that tip. I was getting to something similar, but your contribution really helped me put it together! :-) –  FrodoHackins Oct 30 '12 at 15:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.