Contents !O!l v
4. FORMAL LANGUAGES
4.1 Basic Definitions and Examples
107
4.1.1 Definition of a Grammar
109
4.1.2 Derivations and the Language Generated by a
Grammar
110
4.2 Chomsky Classification of Languages
120
4.3 Languages and Their Relation
123
4.4 Recursive and Recursively Enumerable Sets
124
4.5 Operations on Languages
126
4.6 Languages and Automata
128
4.7 Supplementary Examples
129
Self-Test
132
Exercises
134
107-135
5. REGULAR SETS A~TJ) REGULAR GRAMMARS
136-179
5.1 Regular Expressions
136
5.1.1 Identities for Regular Expressions
138
5.2 Finite Automata and Regular Expressions
140
5.2.1 Transition System Containing A-moves
140
5.2.2 NDFAs with A-moves and Regular Expressions
142
5.2.3 Conversion of Nondeterministic Systems to
Deterministic Systems
146
5.2.4 Algebraic Method Using Arden's Theorem
148
5.2.5 Construction of Finite Automata Equivalent
to a Regular Expression
153
5.2.6 Equivalence of Two Finite Automata
157
5.2.7 Equivalence of Two Regular Expressions
160
5.3 Pumping Lemma for Regular Sets
162
5.4 Application of Pumping Lemma
163
5.5 Closure Properties of Regular Sets
165
5.6 Regular Sets and Regular Grammars
167
5.6.1 Construction of a Regular Grammar Generating
~
T(M) for a Given DFA M
168
5.6.2 Construction of a Transition System M Accepting
L(G) for a Given Regular Grammar G
169
5.7 Supplementary Examples
170
Self- Test
175
Exercises
176
6. CONTEXT·FREE LANGUAGES
6.1 Context-free Languages and Derivation Trees
180
6.1.1 Derivation Trees
181
6.2 Ambiguity in Context-free Grammars
188
18G-226
http://engineeringbooks.net