Automata Theory And Formal Languages
- ISBN/EAN
- 9788854859777
- Editore
- Aracne
- Formato
- Brossura
- Anno
- 2013
- Edizione
- 4
- Pagine
- 272
Disponibile
18,00 €
In this book we present the basic notions of formal language theory and automata theory. In particular, we consider the class of regular languages which are related to the class of finite automata, and the class of the context–free languages which are related to the class of pushdown automata. For the finite automata we also study the problem of their minimalization and the characterization of their behavior using regular expressions. For context–free languages we illustrate how to derive their grammars in Chomsky and Greibach normal form. We study the relationship between deterministic and nondeterministic pushdown automata and the context–free languages they accept. We present also some fundamental techniques for parsing both regular and context–free languages. Then we consider more powerful automata and we illustrate the relationship between linear bounded automata and context–sensitive languages, and between Turing Machines and type 0 languages. A chapter of the book is dedicated to the analysis of various decidability and undecidability problems in context–free languages. In the Appendix we deal with other classes of machines and languages, such as the counter machines, the stack automata, and the abstract families of languages.
Maggiori Informazioni
| Autore | Pettorossi Alberto |
|---|---|
| Editore | Aracne |
| Anno | 2013 |
| Tipologia | Libro |
| Num. Collana | 0 |
| Lingua | Inglese |
| Indice | Preface 7 Chapter 1. Formal Grammars and Languages 9 1.1. Free Monoids 9 1.2. Formal Grammars 10 1.3. The Chomsky Hierarchy 13 1.4. Chomsky Normal Form and Greibach Normal Form 20 1.5. Epsilon Productions 21 1.6. Derivations in Context-Free Grammars 26 1.7. Substitutions and Homomorphisms 29 Chapter 2. Finite Automata and Regular Grammars 31 2.1. Deterministic and Nondeterministic Finite Automata 31 2.2. Nondeterministic Finite Automata and S-extended Type 3 Grammars 35 2.3. Finite Automata and Transition Graphs 37 2.4. Left Linear and Right Linear Regular Grammars 41 2.5. Finite Automata and Regular Expressions 46 2.6. Arden Rule 58 2.7. Equations Between Regular Expressions 59 2.8. Minimization of Finite Automata 61 2.9. Pumping Lemma for Regular Languages 74 2.10. A Parser for Regular Languages 77 2.10.1. A Java Program for Parsing Regular Languages 85 2.11. Generalizations of Finite Automata 93 2.11.1. Moore Machines 94 2.11.2. Mealy Machines 94 2.11.3. Generalized Sequential Machines 95 2.12. Closure Properties of Regular Languages 97 2.13. Decidability Properties of Regular Languages 99 Chapter 3. Pushdown Automata and Context-Free Grammars 103 3.1. Pushdown Automata and Context-Free Languages 103 3.2. From PDA’s to Context-Free Grammars and Back: Some Examples 115 3.3. Deterministic PDA’s and Deterministic Context-Free Languages 121 3.4. Deterministic PDA’s and Grammars in Greibach Normal Form 126 3.5. Simplifications of Context-Free Grammars 128 3.5.1. Elimination of Nonterminal Symbols That Do Not Generate Words 128 3.5.2. Elimination of Symbols Unreachable from the Start Symbol 129 56 CONTENTS 3.5.3. Elimination of Epsilon Productions 130 3.5.4. Elimination of Unit Productions 132 3.5.5. Elimination of Left Recursion 134 3.6. Construction of the Chomsky Normal Form 136 3.7. Construction of the Greibach Normal Form 138 3.8. Theory of Language Equations 146 3.9. Summary on the Transformations of Context-Free Grammars 151 3.10. Self-Embedding Property of Context-Free Grammars 152 3.11. Pumping Lemma for Context-Free Languages 155 3.12. Ambiguity and Inherent Ambiguity 160 3.13. Closure Properties of Context-Free Languages 162 3.14. Basic Decidable Properties of Context-Free Languages 163 3.15. Parsers for Context-Free Languages 164 3.15.1. The Cocke-Younger-Kasami Parser 164 3.15.2. The Earley Parser 167 3.16. Parsing Classes of Deterministic Context-Free Languages 172 3.17. Closure Properties of Deterministic Context-Free Languages 174 3.18. Decidable Properties of Deterministic Context-Free Languages 175 Chapter 4. Linear Bounded Automata and Context-Sensitive Grammars 177 4.1. Recursiveness of Context-Sensitive Languages 186 Chapter 5. Turing Machines and Type 0 Grammars 191 5.1. Equivalence Between Turing Machines and Type 0 Languages 198 Chapter 6. Decidability and Undecidability in Context-Free Languages 203 6.1. Some Basic Decidability and Undecidabilty Results 207 6.1.1. Basic Undecidable Properties of Context-Free Languages 209 6.2. Decidability in Deterministic Context-Free Languages 212 6.3. Undecidability in Deterministic Context-Free Languages 213 6.4. Undecidable Properties of Linear Context-Free Languages 213 Chapter 7. Appendices 215 7.1. Iterated Counter Machines and Counter Machines 215 7.2. Stack Automata 224 7.3. Relationships Among Various Classes of Automata 226 7.4. Decidable Properties of Classes of Languages 230 7.5. Algebraic and Closure Properties of Classes of Languages 233 7.6. Abstract Families of Languages 234 7.7. Finite Automata to/from S-extended Regular Grammars 239 7.8. Context-Free Grammars over Singleton Terminal Alphabets 242 7.9. The Bernstein Theorem 245 7.10. Existence of Functions That Are Not Computable 248 Index 257 Bibliography 265 |
| Disponibilità | Disponibilità: 3-5 gg |
Questo libro è anche in: