[PDF] formal report example for students pdf
[PDF] formal report writing example for students
[PDF] formalin fixation time calculator
[PDF] formalin solution
[PDF] format for project writing pdf
[PDF] format line numbers in word 2016
[PDF] formation developpeur web a distance
[PDF] formatting document in ms word in hindi
[PDF] formatting techniques in tableau
[PDF] forme algébrique d'un nombre complexe exercice
[PDF] forme bilinéaire et quadratique exercices corrigés
[PDF] forme bilinéaire symétrique définie positive
[PDF] forme canonique second degré exercice corrigé
[PDF] forme indéterminée 0/0
[PDF] forme indéterminée math
Alberto Pettorossi
Automata Theory and
Formal Languages
ARACNE
Contents
Preface7
Chapter 1. Formal Grammars and Languages 9
1.1. Free Monoids9
1.2. Formal Grammars10
1.3. The Chomsky Hierarchy13
1.4. Chomsky Normal Form and Greibach Normal Form 19
1.5. Epsilon Productions20
1.6. Derivations in Context-Free Grammars 24
1.7. Substitutions and Homomorphisms 27
Chapter 2. Finite Automata and Regular Grammars 29
2.1. Deterministic and Nondeterministic Finite Automata 29
2.2. Nondeterministic Finite Automata andS-extended Type 3 Grammars 33
2.3. Finite Automata and Transition Graphs 35
2.4. Left Linear and Right Linear Regular Grammars 39
2.5. Finite Automata and Regular Expressions 44
2.6. Arden Rule56
2.7. Equations Between Regular Expressions 57
2.8. Minimization of Finite Automata59
2.9. Pumping Lemma for Regular Languages 72
2.10. A Parser for Regular Languages74
2.10.1. A Java Program for Parsing Regular Languages 82
2.11. Generalizations of Finite Automata 90
2.11.1. Moore Machines91
2.11.2. Mealy Machines91
2.11.3. Generalized Sequential Machines 92
2.12. Closure Properties of Regular Languages 94
2.13. Decidability Properties of Regular Languages 96
Chapter 3. Pushdown Automata and Context-Free Grammars 99
3.1. Pushdown Automata and Context-Free Languages 99
3.2. From PDA"s to Context-Free Grammars and Back: Some Examples 111
3.3. Deterministic PDA"s and Deterministic Context-Free Languages 117
3.4. Deterministic PDA"s and Grammars in Greibach Normal Form 121
3.5. Simplifications of Context-Free Grammars 123
3.5.1. Elimination of Nonterminal Symbols That Do Not Generate Words 123
3.5.2. Elimination of Symbols Unreachable from the Start Symbol 124
5
6CONTENTS
3.5.3. Elimination of Epsilon Productions 125
3.5.4. Elimination of Unit Productions 126
3.5.5. Elimination of Left Recursion129
3.6. Construction of the Chomsky Normal Form 131
3.7. Construction of the Greibach Normal Form 133
3.8. Theory of Language Equations141
3.9. Summary on the Transformations of Context-Free Grammars 146
3.10. Self-Embedding Property of Context-Free Grammars 147
3.11. Pumping Lemma for Context-Free Languages 150
3.12. Ambiguity and Inherent Ambiguity 155
3.13. Closure Properties of Context-Free Languages 157
3.14. Basic Decidable Properties of Context-Free Languages 158
3.15. Parsers for Context-Free Languages 159
3.15.1. The Cocke-Younger-Kasami Parser 159
3.15.2. The Earley Parser162
3.16. Parsing Classes of Deterministic Context-Free Languages 167
3.17. Closure Properties of Deterministic Context-Free Languages 169
3.18. Decidable Properties of Deterministic Context-FreeLanguages 170
Chapter 4. Linear Bounded Automata and Context-Sensitive Grammars 171
4.1. Recursiveness of Context-Sensitive Languages 179
Chapter 5. Turing Machines and Type 0 Grammars 183
5.1. Equivalence Between Turing Machines and Type 0 Languages 190
Chapter 6. Decidability and Undecidability in Context-Free Languages 195
6.1. Some Basic Decidability and Undecidabilty Results 199
6.1.1. Basic Undecidable Properties of Context-Free Languages 201
6.2. Decidability in Deterministic Context-Free Languages 204
6.3. Undecidability in Deterministic Context-Free Languages 205
6.4. Undecidable Properties of Linear Context-Free Languages 205
Chapter 7. Appendices207
7.1. Iterated Counter Machines and Counter Machines 207
7.2. Stack Automata215
7.3. Relationships Among Various Classes of Automata 217
7.4. Decidable Properties of Classes of Languages 221
7.5. Algebraic and Closure Properties of Classes of Languages 224
7.6. Abstract Families of Languages225
7.7. From Finite Automata to Left Linear and Right Linear Grammars 230
7.8. Context-Free Grammars over Singleton Terminal Alphabets 232
7.9. The Bernstein Theorem235
7.10. Existence of Functions That Are Not Computable 237
Index247
Bibliography255
Preface
These lecture notes present some basic notions and results on Automata Theory, Formal Languages Theory, Computability Theory, and Parsing Theory. I prepared these notes for a course on Automata, Languages, and Translators which I am teaching at the University of Roma Tor Vergata. More material on these topics and on parsing techniques for context-free languages can be found in standard textbooks such as [1, 8, 9].The reader is encouraged to look at those books. A theorem denoted by the triplek.m.nis in Chapterkand Sectionm, and within that section it is identified by the numbern. Analogous numbering system is used for algorithms, corollaries, definitions, examples, exercises, figures, and remarks. We use 'iff" to mean 'if and only if". Many thanks to my colleagues of the Department of Informatics, Systems, and Production of the University of Roma Tor Vergata. I am also grateful to my stu- dents and co-workers and, in particular, to Lorenzo Clemente, Corrado Di Pietro, Fulvio Forni, Fabio Lecca, Maurizio Proietti, and Valerio Senni for their help and encouragement. Finally, I am grateful to Francesca Di Benedetto, Alessandro Colombo, Donato Corvaglia, Gioacchino Onorati, and Leonardo Rinaldi of theAracne Publishing Com- pany for their kind cooperation.
Roma, June 2008
In the second edition we have corrected a few mistakes and added Section 7.7 on the derivation of left linear and right linear regular grammars from finite automata and Section 7.8 on context-free grammars with singleton terminal alphabets.
Roma, July 2009
In the third edition we have made a few minor improvements in various chapters.
Roma, July 2011
Alberto Pettorossi
Department of Informatics, Systems, and Production
University of Roma Tor Vergata
Via del Politecnico 1, I-00133 Roma, Italy
pettorossi@info.uniroma2.it http://www.iasi.cnr.it/~adp 7
CHAPTER 1
Formal Grammars and Languages
In this chapter we introduce some basic notions and some notations we will use in the book. The set of natural numbers{0,1,2,...}is denoted byN. Given a setA,|A|denotes the cardinality ofA, and2Adenotes thepowersetofA, that is, the set of all subsets ofA. Instead of2A, we will also writePowerset(A). We say that a setSiscountableiffeitherSis finiteorthere exists a bijection betweenSand the setNof natural numbers.
1.1. Free Monoids
Let us consider a countable setV, also called analphabet. The elements ofVare calledsymbols. Thefree monoid generated by the setVis the set, denotedV?, consisting of all finite sequences of symbols inV, that is, V ?={v1...vn|n≥0and fori= 0,...,n, vi?V}.
The unary operation
?(pronounced 'star") is calledKleene star(orKleene closure, or ?closure). Sequences of symbols are also calledwordsorstrings. Thelengthof a sequencev1...vnisn. The sequence of length0is called theempty sequenceor empty wordand it is denoted byε. The length of a sequencewis also denoted by|w|. Given two sequencesw1andw2inV?, theirconcatenation, denotedw1?w2or simplyw1w2, is the sequence inV?defined by recursion on the length ofw1as follows: w
1?w2=w2ifw1=ε
=v1((v2...vn)?w2)ifw1=v1v2...vnwithn>0. We have that|w1?w2|=|w1|+|w2|. The concatenation operation?is associative and its neutral element is the empty sequenceε. Any set of sequences which is a subset ofV?is called alanguage(or aformal language) over the alphabetV. Given two languagesAandB, theirconcatenation, denotedA?B, is defined as follows: A ?B={w1?w2|w1?Aandw2?B}. Concatenation of languages is associative and its neutral element is the singleton{ε}. WhenBis a singleton, say{w}, the concatenationA?Bwill also be written asA?w or simplyAw. Obviously, ifA=∅orA=∅thenA?B=∅. We have that:V?=V0?V1?V2?...?Vk?..., where for eachk≥0,Vkis the set of all sequences of lengthkof symbols ofV, that is, 9
10 1. FORMAL GRAMMARS AND LANGUAGES
V k={v1...vk|fori= 0,...,k, vi?V}. Obviously,V0={ε},V1=V, and forh,k≥0,Vh?Vk=Vh+k=Vk+h. ByV+ we denoteV?- {ε}. The unary operation+(pronounced 'plus") is calledpositive closureor+closure.
The setV0?V1is also denoted byV0,1.
Given an elementain a setV,a?denotes the set of all finite sequence of zero or morea"s (thus,a?is an abbreviation for{a}?),a+denotes the set of all finite sequence of one or morea"s (thus,a+is an abbreviation for{a}+),a0,1denotes the set{ε,a}(thus,a0,1is an abbreviation for{a}0,1), andaωdenotes the infinite sequence made out of alla"s. Given a wordw, for anyk≥0, theprefix ofwof lengthk, denotedw k, is defined as follows: w
In particular, for anyw, we have that:w
0=εandw|w|=w.
Given a languageL?V?, we introduce the following notation: (i)L0={ε} (ii)L1=L (iii)Ln+1=L?Ln (iv)L?=? k≥0Lk (v)L+=? k>0Lk (vi)L0,1=L0?L1
We also have thatLn+1=Ln?LandL+=L?- {ε}.
Thecomplement of a languageLwith respect to a setV?is the setV?-L. This set is also denoted by¬LwhenV?is understood from the context. The language operation¬is calledcomplementation. From now on, unless otherwise stated, when referring to an alphabet, we will assume that it is a finite set of symbols.quotesdbs_dbs4.pdfusesText_7
[PDF] Automata Theory, Languages,and Computation - Department of