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

Theory of Computation

Created by: Cs Toppers

Computer Science Engineering (CSE) : 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
Read More

Dynamic Test

Content Category

Related Searches

MCQs

,

video lectures

,

Important questions

,

mock tests for examination

,

Free

,

practice quizzes

,

Previous Year Questions with Solutions

,

shortcuts and tricks

,

past year papers

,

Extra Questions

,

Summary

,

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

,

pdf

,

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

,

ppt

,

Objective type Questions

,

study material

,

Sample Paper

,

Semester Notes

,

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

,

Viva Questions

,

Exam

;