# Context free grammar for $1^k0^{2k}$

I need a hint for writing a context-free grammar for the language $L=\{1^k0^{2k}:k\in \mathbb N\}$. I'm starting to doubt that it can be done for general $k$.

• What have you tried? In particular, can you think of a pushdown automaton which accepts this language? Essentially you want the rules of your grammar to allow you to produce as many 1's as you like but you want to ensure that every time you produce a 1 you produce two 0's. The language is regular for a fixed k and it's context-free for general k. – Sam Jones Mar 4 '13 at 23:21
• Can you find a cfg for $\{1^k 0^k \mid k\in\mathbb{N}\}$? Do you see any potential for doubling the number of $1$'s? – Gilles 'SO- stop being evil' Mar 4 '13 at 23:24
• Here is the PDA version: push the ones and each time you read 2 zeros pop the stack. – mrk Mar 4 '13 at 23:30
• @Gilles Yes! That's center-embedded recursion. – mrk Mar 4 '13 at 23:31
• @Gilles Yeah that's like $1^k(00)^k$.. I think I got it right. – mrk Mar 4 '13 at 23:43

$$S \to 1S00 \mid 100$$
• The only case not accounted for is $k=0$, which should generate $\varepsilon$ (unless by $k\in\mathbb{N}$ you mean $k\in\mathbb{N}^{+}$). The fix is simple though, replace $S\rightarrow 100$ with $S\rightarrow \varepsilon$. – Luke Mathieson Mar 5 '13 at 0:25
• @LukeMathieson Yeah it's confusing how mathematicians use $\mathbb N$.. I think of it as being the set of positive natural numbers and I use $\mathbb N_0$ to include $0$. – mrk Mar 5 '13 at 0:29
• Don't worry, mathematicians haven't agreed on what $\mathbb{N}$ is either ;-) – vonbrand Mar 5 '13 at 14:24