1 0

Theory of
q0 q1
1
0 1 1

q2 0
q3
COMPUTATION

Lecture 1: Introduction
Zeinab Abd El Haliem
CSCI419 | Theory of Computation Lecture 1: Introduction 1
Prerequisites

 Math 211 (Discrete Math)

 CSCI 304 (Analysis and Design of Algorithms)

A little refreshment for these courses would help you

progress well in our course 

CSCI419 | Theory of Computation Lecture 1: Introduction 2

Course Information
 Lecture
 Office Hours
 Moodle
 Evaluation
 Policy

CSCI419 | Theory of Computation Lecture 1: Introduction 3

Lectures
Zeinab Abd El Haliem (ZTaha@nu.edu.eg )

 Lecture (2 hrs/week)
 Theoretical and Scientific Background
 Lecture
 Tuesday 8:30- 10:30 & 10:30 – 12:30 & 12:30-2:30 & 2:30- 4:30
 Thursday 2:30- 4:30
 Office Hours
 Thursday 12:30 – 2:30

CSCI419 | Theory of Computation Lecture 1: Introduction 4

Course Grading
Total score 100 degrees

Category Total Number

Final exam 25
Percentages are subject
Midterm 20 1 to changes depending on
Quizzes 15 3 (5) circumstances at the time
Assignments 10 2 (5)
Project 20 2 (10)
Lab Tasks 5
Lecture Contribution 5

CSCI419 | Theory of Computation Lecture 1: Introduction 6

Assignment Submission Policy

 Assignments will be posted on Moodle

 No late submissions are allowed

 If something is not clear, on what constitutes and

what does not, please consult the TA in advance.

CSCI419 | Theory of Computation Lecture 1: Introduction 7

 Assignment Policy
 All assignments must be done individually
 Cheating:
 Helping others, getting help, looking up website for solutions,
etc.
 Students caught cheating will be awarded an F grade
and will be subjected to the NU academic dishonesty
policy.
 Assignments will be checked for Plagiarism
 Detected Cases will be investigated, and penalties may range
from deduction of marks to deprivation of total course work

CSCI419 | Theory of Computation Lecture 1: Introduction 8

Course Objectives
 Introduce concepts in automata theory and
theory of computation
 Design grammars and recognizers for
different formal languages
 Determine the decidability of computational
problems

CSCI419 | Theory of Computation Lecture 1: Introduction 9

Course Organization
 Very broadly, the course will contain three
parts:
1. Automata theory
2. Computability theory
3. Complexity theory

CSCI419 | Theory of Computation Lecture 1: Introduction 10

1. Automata Theory
 We will study simple computing models which
play a crucial role in compilers and
programming languages.
 Finiteautomata, regular languages, and regular
grammars.
 Context free grammars, languages, and pushdown
automata.
 Deterministic and nondeterministic automata.

CSCI419 | Theory of Computation Lecture 1: Introduction 11

2. Computability Theory
 We will define more powerful computing
models to capture general computers and
learn that not all problems are solvable by
computers.
 Turing machines, Church’s thesis, and undecidable
problems.

CSCI419 | Theory of Computation Lecture 1: Introduction 12

3. Complexity Theory
 This theory aims to distinguish decidable
problems in terms of time and space
complexity.
 Time complexity classes P and NP
 Reduction and NP-completeness
 Space complexity

CSCI419 | Theory of Computation Lecture 1: Introduction 13

Course Outline
 Finite automata
 Regular expressions
 Context-free grammars
 Push-down automata
 Nondeterministic Finite Automata
 Chomsky hierarchy of grammars
 Turing machine and the halting problem
 Complexity & NP-Completeness

CSCI419 | Theory of Computation Lecture 1: Introduction 14

Text Books

CSCI419 | Theory of Computation Lecture 1: Introduction 15

Agenda of this lecture

 What is Theory of Computation (TC) ?

 Historical Perspective

 Branches of TC

 Time Complexity of Computational Problems

CSCI419 | Theory of Computation Lecture 1: Introduction 16

 What is TC and how old?
 TC is an accumulation of mathematicians work to make
a model for a machine that can do thinking and
calculations.
 The concept of a machine at early 1900 was a device
that does physical work.
 Scientists’ effort started with a machine that can do
specific calculations like encrypting text using specific
set of steps.
 Alan Turing believed he could invent a generic machine
that can solve more than one type of problems.

CSCI419 | Theory of Computation Lecture 1: Introduction 17

Theory of Computation:
A Historical Perspective
1930s Alan Turing studied
 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
CSCI419 | Theory of Computation Lecture 1: Introduction 18
Alan Turing &
Enigma machine

CSCI419 | Theory of Computation Lecture 1: Introduction

 Let’s hear a Story
 It started before World War II, Germans
army used Enigma encryption.
 Alan Turing and many mathematicians
tried to break the Enigma encryption.
 Their efforts resulted in emergence of a
mechanical device that was dedicated for
deciphering Enigma encrypted messages.
 As a result, many German submarines
were attacked and destroyed.
CSCI419 | Theory of Computation Lecture 1: Introduction 20
Back to TC
 Von Newman, Alan Turing and many
others continued working on creating a
model for a generic machine that can
solve different types of problems.
 The accumulation of their work resulted in
emergence of a collection of theorems
called theory of computation.

CSCI419 | Theory of Computation Lecture 1: Introduction 21

What is TC?
 TC emerged to give answers for
“What are the fundamental capabilities and
limitations of computing machines?”
 Most powerful and modern super computers can NOT
solve some problems!!
 No matter how much processors get fast, no matter
how much memory can be installed; the unsolved
problems remain unsolved!
 We might need lifetime of the universe to find prime
factors of a 500-digits number!

CSCI419 | Theory of Computation Lecture 1: Introduction 22

Why we still need TC?
 Technologies become obsolete but basic theories
remain forever.
 TC provides tools for solving computational
problems like regular expressions for string
parsing and pattern matching.
 Studying different types of grammars like CFG
would help in many other areas like compilers
design and natural language processing.

CSCI419 | Theory of Computation Lecture 1: Introduction 23

 Branches of TC

CSCI419 | Theory of Computation Lecture 1: Introduction 24

Branches of Theory of Computation
mathematical models for computational
Automata
problems such as pattern recognition and
theory other problems

Computability computational models and algorithms for

theory general purpose

Complexity classifying problems according to their

theory difficulty

Computability vs Complexity
Solvable or not Easy or hard
CSCI419 | Theory of Computation Lecture 1: Introduction 25
 Computation

CPU memory

Program memory

CSCI419 | Theory of Computation Lecture 1: Introduction 26

 temporary memory

input

CPU
output

Program memory

CSCI419 | Theory of Computation Lecture 1: Introduction 27

 Example: f(x) = x3

temporary memory

input

CPU
output
Program memory
compute x * x
compute
CSCI419 | Theory of Computation
x 2* x
Lecture 1: Introduction 28
 f(x) = x3

temporary memory

input
x=2

CPU
output
Program memory
compute x * x
compute
CSCI419 | Theory of Computation
x 2* x
Lecture 1: Introduction 29
 temporary memory f(x) = x3
z = 2*2 = 4
f(x) = z*2 = 8

input
x=2

CPU
output
Program memory
compute x * x
compute
CSCI419 | Theory of Computation
x 2* x
Lecture 1: Introduction 30
 temporary memory f(x) = x3
z = 2*2 = 4
f(x) = z*2 = 8

input
x=2

CPU
f(x) = 8
Program memory output
compute x * x
compute
CSCI419 | Theory of Computation
x 2* x
Lecture 1: Introduction 31
 Automaton an abstract
computing
temporary memory device

Automaton
input
CPU
output

Program memory
CSCI419 | Theory of Computation Lecture 1: Introduction 32
 Automaton
temporary memory

Automaton
input

output

state
CSCI419 | Theory of Computation Lecture 1: Introduction 33
Different Kinds of Automata

Automata are distinguished by the temporary memory

Finite Automata No temporary memory

Pushdown Automata stack

Turing Machines Random Access Memory

CSCI419 | Theory of Computation Lecture 1: Introduction 34

 Finite Automaton

temporary memory

input
Finite
Automaton
output

Example: Elevators, Vending Machines

(small computing power)
CSCI419 | Theory of Computation Lecture 1: Introduction 35
 Pushdown Automaton
Stack Push, Pop
temporary
memory

input
Pushdown
Automaton
output

Example: Compilers for Programming Languages, calculator

(medium computing power)

CSCI419 | Theory of Computation Lecture 1: Introduction 36

 Turing Machine

temporary Random Access

memory Memory

input
Turing Machine
output

Example: Any Algorithm

(highest computing power)
CSCI419 | Theory of Computation Lecture 1: Introduction 37
 Power of Automata

Simple More complex Hardest

problems problems problems

Finite Pushdown Turing

Automata Automata Machine

Less power More power

Solve more
computational
problems

CSCI419 | Theory of Computation Lecture 1: Introduction 38

Turing Machine is the most powerful
computational model known
Question:
Are there computational problems that a
Turing Machine cannot solve?

Answer:
Yes (unsolvable problems)

CSCI419 | Theory of Computation Lecture 1: Introduction 39

Time Complexity of Computational
Problems
P problems (Polynomial time problems)

► Solved in polynomial time

NP-complete problems
(Non-deterministic Polynomial time problems)
► Believed to take exponential time to be solved

CSCI419 | Theory of Computation Lecture 1: Introduction 40

References of this lecture
 Lecture notes of the book: Introduction to the
Theory of Computation, Michael Sipser, 3rd
edition
 Prepared by: Ananth Kalyanaraman

 Lecture Notes of Dr. Hussien Sharaf, Computer

Science Department, FCI, Cairo University

CSCI419 | Theory of Computation Lecture 1: Introduction 41

CSCI419 | Theory of Computation Lecture 1: Introduction 42