## Introduction to Formal Languages, Automata Theory and Computation |

### What people are saying - Write a review

User Review - Flag as inappropriate

dfdfdfdf

User Review - Flag as inappropriate

All 6 reviews »This book is a good alternative to the standard one by Ullman &Hopcroft. There is a nice balance between rigour and building intuition. The authors have taken considerable pain to ensure that the book is accessible as a 'first introduction' to the subject without watering down the content. There are large number of worked out examples. There are a large number of exercises for every chapter. Overall this is a very good 'first book' for self study.

### Contents

Grammars | 19 |

Finite State Automata | 57 |

Characterization | 87 |

Finite State Automata with Output | 97 |

Variants of Finite Automata | 111 |

Pushdown Automata | 145 |

ContextFree GrammarsProperties | 165 |

Turing Machines | 193 |

Variations of Turing Machines | 227 |

Universal Turing Machine | 247 |

Time and Space Complexity | 277 |

Recent Trends and Applications | 307 |

New Models of Computation | 357 |

### Common terms and phrases

aaabbb algorithm alphabet ambiguous applied automata automaton binary called cell CFG G Chomsky normal form closure component computation configuration Consider the following construct contains q context-free contextual grammar corresponding crossing sequences defined as follows Definition denoted derivation tree deterministic DFSA elements empty equal number equivalence classes Example family of languages Figure final finite set function given grammar G grammar system graph halting problem halts Hence homomorphism induction infinite initial input tape integer L-systems language accepted length Let G linear mapping Mealy machine mode Moore machine moves left MPCP multiset NFSA node non-deterministic non-terminal NP-complete output pair polynomial polynomial-time reducible problem Proof Let prove pumping lemma pushdown recursively enumerable regular expression regular languages regular set represented satisfiable set of strings simulate Solution stack steps subset Suppose tape head Theorem transition Turing machines undecidable variables