Sun, 15 Jul 2007 18:17:16 -0400

Related articles |
---|

Proof in Hopcroft Automata Book zingard@mcmaster.ca (Daniel Zingaro) (2007-07-15) |

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.