Automata TheoryThis 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. |
O que estão dizendo - Escrever uma resenha
Não encontramos nenhuma resenha nos lugares comuns.
Conteúdo
Mathematical Preliminaries | 1 |
Finite State Automata | 99 |
McNaughtonYamada Theorem | 121 |
Chomsky Grammars | 147 |
Formal Power Series | 215 |
Turing Machines | 249 |
for all tracks | 269 |
Pushdown Automata | 299 |
ContextSensitive Type1 Languages | 329 |
Lindenmeyer Developmental 2 Systems Syntactic | 369 |
Appendices | 387 |
Turing Machine and Complexity | 400 |
References | 419 |
Outras edições - Ver todos
Termos e frases comuns
accept algebraic associated Automata automaton becomes called Chapter Chomsky compute Consider construct contains context-free context-sensitive continued corresponds covered defined Definition Design deterministic elements equivalent Example exists field Figure final finite Formal functions Given grammar halt hand idempotent identity input inverse language length linear means method Modal Logics monoid move non-terminal Note Ø Ø obtain possible problem production rules proof pushdown recursive refer replace semigroup side simple stack Step string studied subgroup symbols Systems tape terminal Theorem Theory transition Turing machine viewed ΔΑ ΔΔ ση συ σψ ψσ ух ху ху
Referências a este livro
Algebraic Theory of Automata Networks: A Introduction Pal Domosi,Chrystopher L. Nehaniv Não há visualização disponível - 2005 |