I found out an exercise where you have to prove the correctness of the following CFG:
Let $L=\{ 0^i 1^j|2i \leq j \leq 3i \}\:$ and $\: G: S\rightarrow 0S11 | 0S111| \epsilon$
claim: Every string $w \in L$ can be generated by $G$.

It says that it's not possible to prove the claim by induction on the length string, and I can't figure out why.

  • 1
    $\begingroup$ The correct parameter to induct on in this case is $i$ rather than the length of the word. However, this induction can be rephrased as induction on the length of the string. $\endgroup$ – Yuval Filmus May 12 '18 at 17:21
  • 3
    $\begingroup$ The obvious thing to would be to try to work out your own proof by induction on the length of the string, and see if the proof works. If you have such a proof, you know the claim is wrong. If you can't find such a proof, maybe that will give you an idea why it is hard. Have you tried that? If so, edit the question to show us what you came up with. If not, give that a try. We want you to only ask questions that you've already put some effort into solving on your own, and to show us what progress you've made so far. $\endgroup$ – D.W. May 12 '18 at 18:39

Your Answer

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

Browse other questions tagged or ask your own question.