PPT - Introduction to Automata Theory Computer Science Engineering (CSE) Notes | EduRev

Computer Science Engineering (CSE): PPT - Introduction to Automata Theory Computer Science Engineering (CSE) Notes | EduRev

The document PPT - Introduction to Automata Theory Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
 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, 1959
Read More

Related Searches

Viva Questions

,

Summary

,

Extra Questions

,

PPT - Introduction to Automata Theory Computer Science Engineering (CSE) Notes | EduRev

,

Semester Notes

,

MCQs

,

pdf

,

ppt

,

past year papers

,

Important questions

,

Objective type Questions

,

Previous Year Questions with Solutions

,

PPT - Introduction to Automata Theory Computer Science Engineering (CSE) Notes | EduRev

,

video lectures

,

study material

,

PPT - Introduction to Automata Theory Computer Science Engineering (CSE) Notes | EduRev

,

shortcuts and tricks

,

practice quizzes

,

Exam

,

Sample Paper

,

mock tests for examination

,

Free

;