Proof in Hopcroft Automata Book

From: Daniel Zingaro <zingard@xxxxxxxxxxx>
Date: Sun, 15 Jul 2007 18:17:16 -0400

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

.

Prev by Date: Re: Integers on 64-bit machines
Next by Date: ELF wrapper around COFF
Previous by thread: Call-for-participation: ACSAC 2007 (Korea, Aug 07)
Next by thread: ELF wrapper around COFF
Index(es):
- Date
- Thread

Relevant Pages

Re: Regualar Expression Theory
... Papadimitriou taught a class in foundational papers which contributed to ... Element of the Theory of Computation, Prentice Hall, 2nd Edition, 1998. ... Introduction to Automata Theory, Languages, and Computation, ... Model of Computation and Formal Languages, Oxford University Press, 1997. ...
(comp.unix.shell)
Re: show that pdas are more powerful than dpdas
... languages: Hopcroft, Ullman and Motwani" go straight to the chapter on ...
(comp.theory)