## An Introduction to Formal Languages and AutomataFormal languages, automata, computability, and related matters form the major part of the theory of computation. This textbook is designed for an introductory course for computer science and computer engineering majors who have knowledge of some higher-level programming language, the fundamentals of |

### What people are saying - Write a review

User Review - Flag as inappropriate

nice book

User Review - Flag as inappropriate

Nice Book................

### Contents

Introduction to the Theory of Computation | 2 |

Finite Automata | 35 |

Accepters | 55 |

Regular Languages and Regular Grammars | 71 |

Grammars | 95 |

ContextFree Languages | 125 |

Simplification of ContextFree Grammars | 149 |

Pushdown Automata | 175 |

Turing Machines | 221 |

Other Models of Turing Machines | 249 |

A Hierarchy of Formal Languages and Automata | 275 |

Limits of Algorithmic Computation | 299 |

Other Models of Computation | 323 |

An Introduction to Computational Complexity | 343 |

Answers to Selected Exercises | 357 |

405 | |

### Other editions - View all

### Common terms and phrases

A-productions accepts the language anbn argument assume closure complement complete computation configuration Consider construction context-free grammar control unit countable defined definition denoted derivation tree deterministic context-free language dfa's DTIME edge equivalent Exercise exists final Find finite accepter finite number following languages formal give given grammar G Greibach normal form halting problem induction initial integers labeled language accepted language families languages is closed leftmost linear bounded automaton move nondeterminism nondeterministic npda number of a's pair parsing PC-solution Post correspondence problem Post system primitive recursive productions programming languages proof prove pumping lemma pushdown automata read-write head recursively enumerable languages regular expression regular grammar regular languages removed result s-grammar Section sentential form sequence Show shown in Figure simple simulate solution stack standard Turing machine step subset substring tape terminal Theorem transition function transition graph undecidable unit-productions unrestricted grammar variable vertex