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