Proof in Hopcroft Automata Book

Daniel Zingaro <zingard@mcmaster.ca>
Sun, 15 Jul 2007 18:17:16 -0400

          From comp.compilers
Related articles
Proof in Hopcroft Automata Book zingard@mcmaster.ca (Daniel Zingaro) (2007-07-15)
| List of all articles for this month |
From: Daniel Zingaro <zingard@mcmaster.ca>
Newsgroups: comp.compilers
Date: Sun, 15 Jul 2007 18:17:16 -0400
Organization: Compilers Central
Keywords: theory, question
Posted-Date: 17 Jul 2007 11:41:45 EDT

Hi all,


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,
Dan


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.