0
$\begingroup$

I needed help finding the context free grammar of this string

$$ 10^{n}10^{n}1 $$

So far an idea I have is $$ S\rightarrow 1S1S1\mid 0S \mid \varepsilon $$

Any assistance you can provide would be greatly appreciated!

$\endgroup$
1
  • $\begingroup$ You need to "couple" the sites where you need to create the same number of symbols. Are you able to come up with a grammar for $0^n1^n$? (Also, we have a reference question for these things but I'm not sure how much help it'll be for you. $\endgroup$
    – Raphael
    Oct 7, 2014 at 6:10

2 Answers 2

3
$\begingroup$

When looking for CFGs for an expression like yours, it is often handy to work from the inside out, especially whan you need to match symbols. Think of your expression as $1(0^n10^n)1$. The interior part, within the parentheses, consists of a $1$ surrounded by an equal number of zeros on each side. We could generate this by the production $T\rightarrow 0T0$, since repeated use of this production would result in derivations like $$ T\Rightarrow 0T0\Rightarrow 00T00\Rightarrow 000T000 $$ and so on. In other words, we could have $T\stackrel{*}{\Rightarrow} 0^nT0^n$, where the star over the arrow means "eventually results in". Now all you have to do is get the $1$ in the middle. That's easy: just add the production $T\rightarrow 1$. In sum, you can get the part in parentheses by the productions $$ T\rightarrow 0T0\mid 1 $$ Now that you have the middle part, just add the external $1$s to a start variable production $S\rightarrow 1T1$, giving the full grammar $$\begin{align} S&\rightarrow 1T1\\ T&\rightarrow 0T0\mid 1 \end{align}$$

Your attempt was a good start, since you did generate the correct number of $1$s, but there was no guarantee that the two $S$ variables in $S\rightarrow1S1S1$ would generate the matching $0$s you need.

$\endgroup$
2
  • $\begingroup$ Interesting remark. $\endgroup$
    – babou
    Oct 7, 2014 at 11:07
  • $\begingroup$ This is exactly what I was looking for! Thank you $\endgroup$
    – Zee
    Oct 7, 2014 at 13:26
3
$\begingroup$

This answer was inspired by Rick Decker's answer. I thought he made an interesting remark about working inside out, and I tried to replace it in a more general understanding of context-freeness.

Context-free grammars are often (actually always) elaborate ways of writing ornate strings of well nested parentheses, possibly of different shapes (see Chomsky-Schutzenberger second theorem). One problem is usually to see the parentheses hidden behing the ornaments. In your case, it is pretty easy, because even though the opening and closing parentheses hide behind the same ornament $0$, they betray themselves because it is specified that the two sequences of zeros have the same length, like a sequence of opening parentheses followed by a sequence of closing ones.

Hence, it becomes quite natural to try to generate these as parentheses.

Now, if you are asked to generate $(^nw)^n$, where $w$ is any string, it is quite natural to write the rule $X\to (X)\mid w$. Then all you have to do is replace the parentheses by $0$, both opening and closing parentheses, an to replace $w$ by $1$ (that is called a homomorphism in the Chomsky-Schutzenberger theorem). This gives you $X\to 0X0\mid 1$.

I leave the rest to you.

On Raphael's suggestion, for more techniques to build a CF grammar, see this page which also describes in more detail the Chomsky-Schutzenberger theorem

$\endgroup$
6
  • $\begingroup$ See also here. $\endgroup$
    – Raphael
    Oct 7, 2014 at 12:08
  • $\begingroup$ Thinking about it, it appears that this inside-out way of thinking about making a grammar is more nearly universal than I thought, since a Dyck language is a natural candidate for this approach and since every CFL is (the homomorphic image of) a Dyck language (intersected with a regular language). For example, the language consisting of all strings over $a, b$ with the same number of $a$s and $b$s is just the image of the Dyck language on two kinds of parentheses, making the CFG particularly easy to find. $\endgroup$ Oct 7, 2014 at 21:11
  • $\begingroup$ @RickDecker This is precisely how your answer inspired mine. What you describe is the Chomsky-Schutzenberger second theorem. But then, the homomorphism can be pretty effective in confusing things, and the regular set may be non trivial. But that is the price for CF to be useful. :) $\endgroup$
    – babou
    Oct 7, 2014 at 21:30
  • $\begingroup$ @Raphael If I remembered better what is available, I would avoid such repeats. Oh well ... At l(e)ast I included your reference. $\endgroup$
    – babou
    Oct 7, 2014 at 21:45
  • 1
    $\begingroup$ Putting on my professor hat, though, I think that one could come up with a bunch of "inside-out" approaches that, while based on the C-S2 theorem, hide it sufficiently that students at an early stage would appreciate it (which is what I was trying to do with the OP). $\endgroup$ Oct 7, 2014 at 23:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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