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

 Page 1


Courtesy: Costas Busch / Jeff Ullman 1
CS-208
Theory of Computation
Slides have been modified by Shaukat Wasi – CS@DSU
Page 2


Courtesy: Costas Busch / Jeff Ullman 1
CS-208
Theory of Computation
Slides have been modified by Shaukat Wasi – CS@DSU
Human
• A machine that 
– recognizes one/multiple languages
– performs useful work when given instructions 
in the recognized language (s)
– has a capability of processing the 
instructions/input to
• Solve a set of problems [NOT ALL Problems]
Courtesy: Costas Busch / Jeff Ullman 2
Page 3


Courtesy: Costas Busch / Jeff Ullman 1
CS-208
Theory of Computation
Slides have been modified by Shaukat Wasi – CS@DSU
Human
• A machine that 
– recognizes one/multiple languages
– performs useful work when given instructions 
in the recognized language (s)
– has a capability of processing the 
instructions/input to
• Solve a set of problems [NOT ALL Problems]
Courtesy: Costas Busch / Jeff Ullman 2
Human Capabilities
• To judge the capabilities of humans (in 
general) with respect to:
– What problems can be solved by humans?
• Can’t experiments with all humans…
• We would like to develop an abstract model 
of humans
– Processing Model (Abstract Machine) [IPO]
– A set of problems
Courtesy: Costas Busch / Jeff Ullman 3
Page 4


Courtesy: Costas Busch / Jeff Ullman 1
CS-208
Theory of Computation
Slides have been modified by Shaukat Wasi – CS@DSU
Human
• A machine that 
– recognizes one/multiple languages
– performs useful work when given instructions 
in the recognized language (s)
– has a capability of processing the 
instructions/input to
• Solve a set of problems [NOT ALL Problems]
Courtesy: Costas Busch / Jeff Ullman 2
Human Capabilities
• To judge the capabilities of humans (in 
general) with respect to:
– What problems can be solved by humans?
• Can’t experiments with all humans…
• We would like to develop an abstract model 
of humans
– Processing Model (Abstract Machine) [IPO]
– A set of problems
Courtesy: Costas Busch / Jeff Ullman 3
Problems solvable by Humans
• Recognition of a Language
– A Problem (itself) 
• Hence
– Language =  Problem ?
• Is language ‘x’ recognizable by the machine?
• Is problem ‘x’ solvable by the machine?
• We (in this course) will focus mainly on this 
simple Problem (w.r.t Computers)
Courtesy: Costas Busch / Jeff Ullman 4
Page 5


Courtesy: Costas Busch / Jeff Ullman 1
CS-208
Theory of Computation
Slides have been modified by Shaukat Wasi – CS@DSU
Human
• A machine that 
– recognizes one/multiple languages
– performs useful work when given instructions 
in the recognized language (s)
– has a capability of processing the 
instructions/input to
• Solve a set of problems [NOT ALL Problems]
Courtesy: Costas Busch / Jeff Ullman 2
Human Capabilities
• To judge the capabilities of humans (in 
general) with respect to:
– What problems can be solved by humans?
• Can’t experiments with all humans…
• We would like to develop an abstract model 
of humans
– Processing Model (Abstract Machine) [IPO]
– A set of problems
Courtesy: Costas Busch / Jeff Ullman 3
Problems solvable by Humans
• Recognition of a Language
– A Problem (itself) 
• Hence
– Language =  Problem ?
• Is language ‘x’ recognizable by the machine?
• Is problem ‘x’ solvable by the machine?
• We (in this course) will focus mainly on this 
simple Problem (w.r.t Computers)
Courtesy: Costas Busch / Jeff Ullman 4
Theory of Computation
• Theory of computation is the branch that deals 
with how efficiently problems can be solved on 
a Model of Computation, using an Algorithm. 
• The field is divided into three major branches:
– Automata Theory and language ,
– Computability Theory,
– Computational Complexity Theory [Efficiency], 
• Which are linked by the question: "What are the 
fundamental capabilities and limitations of 
computers?"
Courtesy: Costas Busch / Jeff Ullman 5