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

  • 1
    $\begingroup$ 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. $\endgroup$ – Sam Jones Mar 4 '13 at 23:21
  • 4
    $\begingroup$ 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? $\endgroup$ – Gilles 'SO- stop being evil' Mar 4 '13 at 23:24
  • $\begingroup$ Here is the PDA version: push the ones and each time you read 2 zeros pop the stack. $\endgroup$ – mrk Mar 4 '13 at 23:30
  • $\begingroup$ @Gilles Yes! That's center-embedded recursion. $\endgroup$ – mrk Mar 4 '13 at 23:31
  • 1
    $\begingroup$ @Gilles Yeah that's like $1^k(00)^k$.. I think I got it right. $\endgroup$ – mrk Mar 4 '13 at 23:43

Based on the comments:

$$S \to 1S00 \mid 100$$

  • 1
    $\begingroup$ 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$. $\endgroup$ – Luke Mathieson Mar 5 '13 at 0:25
  • $\begingroup$ @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$. $\endgroup$ – mrk Mar 5 '13 at 0:29
  • $\begingroup$ Don't worry, mathematicians haven't agreed on what $\mathbb{N}$ is either ;-) $\endgroup$ – vonbrand Mar 5 '13 at 14:24
  • $\begingroup$ @vonbrand Indeed. Hey do you have a personal website? $\endgroup$ – mrk Mar 5 '13 at 14:25
  • $\begingroup$ No personal website $\endgroup$ – vonbrand Mar 5 '13 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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