PPT: Introduction & Automata | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


1
Introduction to Automata Theory
Page 2


1
Introduction to Automata Theory
What is Automata Theory?
2
?
Study of abstract computing devices, or 
“machines”
?
Automaton = an abstract computing device
?
Note: A “device” need not even be a physical hardware!
?
A fundamental question in computer science: 
?
Find out what different models of machines can do and 
cannot do
?
The theory of computation
?
Computability vs. Complexity
Page 3


1
Introduction to Automata Theory
What is Automata Theory?
2
?
Study of abstract computing devices, or 
“machines”
?
Automaton = an abstract computing device
?
Note: A “device” need not even be a physical hardware!
?
A fundamental question in computer science: 
?
Find out what different models of machines can do and 
cannot do
?
The theory of computation
?
Computability vs. Complexity
Alan Turing (1912-1954)
3
?
Father of Modern Computer 
Science
?
English mathematician
?
Studied abstract machines called 
Turing machines even before 
computers existed
?
Heard of the Turing test?
(A pioneer of automata theory)
Page 4


1
Introduction to Automata Theory
What is Automata Theory?
2
?
Study of abstract computing devices, or 
“machines”
?
Automaton = an abstract computing device
?
Note: A “device” need not even be a physical hardware!
?
A fundamental question in computer science: 
?
Find out what different models of machines can do and 
cannot do
?
The theory of computation
?
Computability vs. Complexity
Alan Turing (1912-1954)
3
?
Father of Modern Computer 
Science
?
English mathematician
?
Studied abstract machines called 
Turing machines even before 
computers existed
?
Heard of the Turing test?
(A pioneer of automata theory)
Theory of Computation: A Historical Perspective
4
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
What is Automata Theory?
2
?
Study of abstract computing devices, or 
“machines”
?
Automaton = an abstract computing device
?
Note: A “device” need not even be a physical hardware!
?
A fundamental question in computer science: 
?
Find out what different models of machines can do and 
cannot do
?
The theory of computation
?
Computability vs. Complexity
Alan Turing (1912-1954)
3
?
Father of Modern Computer 
Science
?
English mathematician
?
Studied abstract machines called 
Turing machines even before 
computers existed
?
Heard of the Turing test?
(A pioneer of automata theory)
Theory of Computation: A Historical Perspective
4
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
Languages & Grammars
?
Languages: “A language is a 
collection of sentences of 
finite length all constructed 
from a finite alphabet of 
symbols”
?
Grammars: “A grammar can 
be regarded as a device that 
enumerates the sentences of 
a language” - nothing more, 
nothing less
?
N. Chomsky, Information 
and Control, Vol 2, 1959
5
Or “words”
Image source: Nowak et al. Nature, vol 417, 2002