Automata Theory

Capa
World Scientific, 1999 - 428 páginas
This book covers substantially the central ideas of a one semester course in automata theory. It is oriented towards a mathematical perspective that is understandable to non-mathematicians. Comprehension is greatly aided by many examples, especially on the Chomsky ? Sch tzenberger theorem, which is not found in most books in this field. Special attention is given to semiautomata theory: the relationship between semigroups and sequential machines (including Green's relations), Sch tzenberger's maximal subgroup, von Neumann inverses, wreath products, transducers using matrix notation, shuffle and Kronecker shuffle products. Methods of formal power series, the ambiguity index and linear languages are discussed. Core material includes finite state automata, regular expressions, Kleene's theorem, Chomsky's hierarchy and transformations of grammars. Ambiguous grammars (not limited to context-free grammars) and modal logics are briefly discussed. Turing machine variants with many examples, pushdown automata and their state transition diagrams and parsers, linear-bounded automata/2-PDA and Kuroda normal form are also discussed. A brief study of Lindenmeyer systems is offered as a comparison to the theory of Chomsky.
 

Conteúdo

Chapter
1
Semigroup Decompositions
34
Serial Product Decomposition
73
Topological Graph Theory Applied to Sequential Machines
79
Finite State Automata
99
Conversion of NDFSA into DFSA
106
The McNaughtonYamada Theorem
117
Reduced Finite State Automata
124
Chomsky Grammars
147
Formal Power Series
215
Turing Machines
249
Pushdown Automata
299
ContextSensitive Type1 Languages
329
Lindenmeyer Developmental 4 Systems Syntactic
369
Appendices
387
Turing Machine and Complexity
400

Transducers
133
Kronecker Product
140
References
419
Direitos autorais

Outras edições - Ver todos

Termos e frases comuns

Referências a este livro

Informações bibliográficas