Automata theory

The automata theory is a branch of theoretical computer science that deals with the study of automata (model computers ) and with the problems that these automata can solve .

It is an important tool in computability theory and complexity theory . It finds practical application in the design of lexical scanners and parsers in compiler construction as well as for the design of programming languages .

Automata theory deals with formal languages and formal grammars , which, among other things, a. typified by the Chomsky hierarchy , and with models for automata that can process such languages, in particular finite automata , push-down automata , cellular automata, and Turing machines .

literature

Dieter Schulte: Combinatorial and Sequential Networks: Fundamentals and Applications of Automata Theory , Oldenbourg , Munich 1967
Claude Elwood Shannon , John McCarthy (eds.): Studies on the theory of automata , Rogner & Bernhard , Munich 1974 (translation of an original anthology published in 1956 with contributions by, among others, John von Neumann , Stephen Cole Kleene , Edward F. Moore , Marvin Minsky )
Horst H. Homuth: Introduction to automaton theory for students of mathematics, computer science, natural and engineering sciences , Vieweg Verlag , Braunschweig 1977
John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages and Complexity Theory , 2nd, revised. Ed., Pearson Education Germany , Munich 2003
Uwe Schöning : Theoretical Computer Science - Briefly , 5., revised. Ed., Spektrum Akademischer Verlag , Heidelberg, 2003
Jan Lunze: Discrete event systems: Modeling and analysis of dynamic systems with automata, Markov chains and Petri nets , Oldenbourg, 2006, ISBN 3-486-58071-X

Commons : Automata Theory - collection of pictures, videos and audio files

Wiktionary: automata theory - explanations of meanings, word origins, synonyms, translations