Page 1 1 Introduction to Automata Theory Page 2 1 Introduction to Automata Theory 2 What is Automata Theory? n Study of abstract computing devices, or “machines” n Automaton = an abstract computing device n Note: A “device” need not even be a physical hardware! n A fundamental question in computer science: n Find out what different models of machines can do and cannot do n The theory of computation n Computability vs. Complexity Page 3 1 Introduction to Automata Theory 2 What is Automata Theory? n Study of abstract computing devices, or “machines” n Automaton = an abstract computing device n Note: A “device” need not even be a physical hardware! n A fundamental question in computer science: n Find out what different models of machines can do and cannot do n The theory of computation n Computability vs. Complexity 3 Alan Turing (1912-1954) n Father of Modern Computer Science n English mathematician n Studied abstract machines called Turing machines even before computers existed n Heard of the Turing test? (A pioneer of automata theory) Page 4 1 Introduction to Automata Theory 2 What is Automata Theory? n Study of abstract computing devices, or “machines” n Automaton = an abstract computing device n Note: A “device” need not even be a physical hardware! n A fundamental question in computer science: n Find out what different models of machines can do and cannot do n The theory of computation n Computability vs. Complexity 3 Alan Turing (1912-1954) n Father of Modern Computer Science n English mathematician n Studied abstract machines called Turing machines even before computers existed n Heard of the Turing test? (A pioneer of automata theory) 4 Theory of Computation: A Historical Perspective 1930s Alan Turing studies Turing machines Decidability Halting problem 1940-1950s “Finite automata” machines studied Noam Chomsky proposes the “Chomsky Hierarchy” for formal languages 1969 Cook introduces “intractable” problems or “NP-Hard” problems 1970- Modern computer science: compilers, computational & complexity theory evolve Page 5 1 Introduction to Automata Theory 2 What is Automata Theory? n Study of abstract computing devices, or “machines” n Automaton = an abstract computing device n Note: A “device” need not even be a physical hardware! n A fundamental question in computer science: n Find out what different models of machines can do and cannot do n The theory of computation n Computability vs. Complexity 3 Alan Turing (1912-1954) n Father of Modern Computer Science n English mathematician n Studied abstract machines called Turing machines even before computers existed n Heard of the Turing test? (A pioneer of automata theory) 4 Theory of Computation: A Historical Perspective 1930s Alan Turing studies Turing machines Decidability Halting problem 1940-1950s “Finite automata” machines studied Noam Chomsky proposes the “Chomsky Hierarchy” for formal languages 1969 Cook introduces “intractable” problems or “NP-Hard” problems 1970- Modern computer science: compilers, computational & complexity theory evolve 5 Languages & Grammars Or “words” Image source: Nowak et al. Nature, vol 417, 2002 n Languages: “A language is a collection of sentences of finite length all constructed from a finite alphabet of symbols” n Grammars: “A grammar can be regarded as a device that enumerates the sentences of a language” - nothing more, nothing less n N. Chomsky, Information and Control, Vol 2, 1959Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests