|Proof in Hopcroft Automata Book email@example.com (Daniel Zingaro) (2007-07-15)|
|From:||Daniel Zingaro <firstname.lastname@example.org>|
|Date:||Sun, 15 Jul 2007 18:17:16 -0400|
On page 190 of "Introduction to Automata Theory, Languages and
Computation", 2E, Hopcroft et al., there is an observation about
derivability in CFG's. It states that if x1x2...xk =*>w, then we can
break w into w1w2... such that xi =*> wi. This makes sense, but I'm
wondering if anyone can further explain Hopcroft's proof hint that he
gives below this observation? Specifically, I can't figure out the
precise inductive hypothesis that is required, and why it allows us to
conclude the theorem.
Thanks for any ideas,
Return to the
Search the comp.compilers archives again.