CS200
Models of Computation
1
General Info
Book: Introduction to Automata
Theory, Languages and Computation
Hopcroft, Motwani and Ullman, 3nd edition
Shashidhar G. Koolagudi
NITK, Surathkal
Course plan will be supplied shortly
2
Computation
CPU memory
3
temporary memory
input
CPU
output
Program memory
4
3
Example: f ( x ) x
temporary memory
input
CPU
output
Program memory
compute xx
2
compute x x
5
3
f ( x) x
temporary memory
input
x 2
CPU
output
Program memory
compute xx
2
compute x x
6
3
temporary memory f ( x) x
z 2 * 2 4
f ( x) z * 2 8
input
x 2
CPU
output
Program memory
compute xx
2
compute x x
7
3
Temporary Memory f ( x) x
z 2 * 2 4
f ( x) z * 2 8
input
x 2
CPU
f ( x) 8
Program Memory output
compute xx
2
compute x x
8
Automaton
Temporary Memory
Automaton
input
CPU
output
Program memory
9
Automaton
Temporary Memory
Automaton
input
output
transition
state
10
Different Kinds of Automata
Automata are distinguished by the temporary memo
• Finite Automata: no temporary memory
• Pushdown Automata: stack (Memory)
• Turing Machines: random access memory
11
Finite Automaton
temporary memory
input
Finite
Automato
n
output
Example: Elevators, Vending Machines
(small computing power)
12
Pushdown Automaton
Temp.
memory Stack Push, Pop
Pushdown input
Automaton
output
Example: Compilers for Programming Languages
(medium computing power)
13
Turing Machine
Temp.
memory Random Access
Memory
input
Turing
Machine
output
Examples: Any Algorithm
(highest computing power)
14
Power of Automata
Simple More complex Hardest
problems problems problems
Finite Pushdown Turing
Automata Automata Machine
Less power More power
Solve more
computational problems
15
Turing Machine is the most powerful
computational model known
Question: Are there computational
problems that a Turing Machine
cannot solve?
Answer: Yes (unsolvable problems)
16
Time Complexity of Computational Problems:
NP-complete problems
Believed to take exponential
time to be solved
P problems
Solved in polynomial time
17