Automata TheoryWorld 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 |
Outras edições - Ver todos
Termos e frases comuns
A₁ a² a³ a³ a² ab)² Automata Theory automaton B₁ B₂ ba)² Chapter Chomsky compute construct context-free context-free grammar context-free languages context-sensitive context-sensitive languages deterministic Example Figure finite formal power series G₁ grammar Green's relations H₁ idempotent Kuroda Normal Form language Linear-Bounded LR(k M₁ M₂ Modal Logics monoid non-terminal Note Ø Ø production rules Pushdown Automata q₁ R₁ R₁₁ R₁₂ recursive regular expressions S₁ Schützenberger semigroup T₁ T₂ tape Theorem Turing machine w₁ y₁ y²x yx yx yx² Δ Δ Δ δι δι ΔΙΔ ΔΧ Ι Δ λ λ σ σ σ σψ σ'ψε σ² στ συ συσ σψ σ σψ σψ σψε τσ Χ Δ Ψ Ψ ψε ψισ ψοσ ψσ
Referências a este livro
Algebraic Theory of Automata Networks: An Introduction Pal Domosi,Chrystopher L. Nehaniv Prévia não disponível - 2005 |