Parsing family of grammars, determine if LR(k)

I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him personally. So I apologize, but I do have to ask for your help!

Would it be enough to show that the formula works for n = 2, n = 3 (by drawing the automata) and deduct that it must work for any n?

As for the second question, could I follow the same strategy?

Thank you for you time.

  • $\begingroup$ Please make your questions self-contained, so we have all relevant context in your question itself (without having to follow some other link to understand what you are asking). $\endgroup$ – D.W. Nov 30 '14 at 20:10
  • $\begingroup$ I know I should, it's just that I have the exact same questions so I didn't wanna copy paste the whole thing. $\endgroup$ – Xpl0 Nov 30 '14 at 21:21

No, of course not. If you want to prove that some formula is true for all $n$, it is in general not enough to show that it is true for $n=2$ and $n=3$. That's just wishful thinking.

Consider, for instance, the claim that $n^2+n+41$ is prime for all $n$. You can check it for $n=2$ (sure enough, $2^2+2+41=47$ is prime) and $n=3$ (yup, $3^2+3+41=53$ is prime), and it'll be true for both $n=2$ and $n=3$, but that doesn't mean it's true for all $n$. In fact, it's not true for all $n$: at $n=41$, the corresponding value is not prime (it is divisible by 41).

| cite | improve this answer | |
  • $\begingroup$ In fact, it first fails for $n=40$. $\endgroup$ – Rick Decker Nov 30 '14 at 21:14
  • $\begingroup$ @D.W. So what would you suggest? Could I use induction somehow? $\endgroup$ – Xpl0 Nov 30 '14 at 21:22
  • $\begingroup$ @Xpl0, see the other question. If that one hasn't gotten an answer, maybe it's not of interest to people here; asking again won't change anything. When you get more rep you can offer a bounty on that question if you want. $\endgroup$ – D.W. Nov 30 '14 at 21:44

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.