Automata Theory
, Theory of Computation 1
Instructor: Hassan Kassim Mohammad
Theory of computation is the theoretical study of capabilities and limitations of Computers (Theoretical
models of computation).
Objectives:
Providing students with:
o an understanding of basic concepts in the theory of computation through simple models of
computational devices.
o apply models in practice to solving problems in diverse areas such as string searching, pattern
matching, cryptography, and language design;
o understand the limitations of computing, the relative power of formal languages and the inherent
complexity of many computational problems.
o be familiar with standard tools and notation for formal reasoning about machines and programs.
REFERENCES:
1. Introduction to Computer Theory 2nd Edition
Daniel I. A. Cohen John Wiley & Sons, Inc 1997. ISBN 0-471-13772-3
2. Introduction to Automata Theory, Languages, and Computation, 2/E,
John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman, Addison-Wesley 2001. ISBN 0-201-44124-1.
Units: 6
Grading Policy
Semester Exam Attendance Assignments & Quizzes Total
1st semester 10 2 3 15
2nd semester 10 2 3 15
Final 70 - - 70
Notes
Student must attend at least 80% of total classes to pass the course.
Any kind of cheating/plagiarism may result in a Fail grade in the course.
No labs. But you should write some programs with any language you may know.
There will be about 30 lectures 100 minutes each.
Late homework submissions will be penalized
Office Hours
Sunday, Monday, Tuesday, Wednesday
Contact Information
Office: computer science dept. room no. 67
E-mail:
Mustansiriya University – college of sciences – computer science department – second class
, Theory of Computation 2
Syllabus
Week Date Subject Chapter
Introduction, terminology, definitions 1
Sets and operations 1
languages 2
Regular Expressions RE 4
Finite Automata FA 5
Deterministic Finite Automaton DFA 5
Non Deterministic Finite Automaton NDFA 8
Language Accepted by Finite Automata 5
Convert Regular Expression into NFA
Constructing regular expression from Finite Automata
Finite Automata with Epsilon moves
Moore and Mealy machines 9
Converting between Moore and Mealy machine
Pumping lemma for regular languages
Kleene's Theorem 7
Regular Grammar 10
Myhill-Nerode Theorem Minimization of DFA
EXAM
Context-free Languages 13
Pushdown Automata 17
CFG/CFL to PDA 18
PDA to CFG/CFL
CFG derivation trees Parsing 22
Chomsky normal form 16
Greibach normal form 16
Ambiguous CFL's
EXAM
TURING MACHINES TM 24
COMPUTABILITY and COMPLEXITY
Unsolvable Problems
Time Complexity
CYK algorithm for CFG's
CFL pumping lemma and properties
Church Turing Thesis
Mustansiriya University – college of sciences – computer science department – second class
, Theory of Computation 3
As a computer IT, you must study the following:
1- Automata and formal language.
Which answers - What are computers (Or what are models of computers)
2- Compatibility.
Which answers - What can be computed by computers?
3- Complexity.
Which answers - What can be efficiently computed?
In automata we will simulates parts of computers. Or we will make mathematical models of computers
Automata are more powerful than any real computer because we can design any machine on papers that can
do everything we want.
Theory of computation is the theoretical study of capabilities and limitations of Computers
(Theoretical models of computation).
Sets
Let A, B, and C be subsets of the universal set U
Distributive properties
A (B U C) (A B) U (A C
A U (B C) (A U B) (A U C
Idempotent properties
A A A,
AUA A.
Double Complement property
(A ) A.
De Morgan’s laws
(A U B) A B
(A B) A UB
Commutative properties
A B B A,
AUB B U A.
Associative laws
A (B C) (A B) C
A U (B U C) (A U B) U C
Identity properties
AU A,
A U A.
Complement properties
AUA U,
A A .
Mustansiriya University – college of sciences – computer science department – second class
, Theory of Computation 1
Instructor: Hassan Kassim Mohammad
Theory of computation is the theoretical study of capabilities and limitations of Computers (Theoretical
models of computation).
Objectives:
Providing students with:
o an understanding of basic concepts in the theory of computation through simple models of
computational devices.
o apply models in practice to solving problems in diverse areas such as string searching, pattern
matching, cryptography, and language design;
o understand the limitations of computing, the relative power of formal languages and the inherent
complexity of many computational problems.
o be familiar with standard tools and notation for formal reasoning about machines and programs.
REFERENCES:
1. Introduction to Computer Theory 2nd Edition
Daniel I. A. Cohen John Wiley & Sons, Inc 1997. ISBN 0-471-13772-3
2. Introduction to Automata Theory, Languages, and Computation, 2/E,
John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman, Addison-Wesley 2001. ISBN 0-201-44124-1.
Units: 6
Grading Policy
Semester Exam Attendance Assignments & Quizzes Total
1st semester 10 2 3 15
2nd semester 10 2 3 15
Final 70 - - 70
Notes
Student must attend at least 80% of total classes to pass the course.
Any kind of cheating/plagiarism may result in a Fail grade in the course.
No labs. But you should write some programs with any language you may know.
There will be about 30 lectures 100 minutes each.
Late homework submissions will be penalized
Office Hours
Sunday, Monday, Tuesday, Wednesday
Contact Information
Office: computer science dept. room no. 67
E-mail:
Mustansiriya University – college of sciences – computer science department – second class
, Theory of Computation 2
Syllabus
Week Date Subject Chapter
Introduction, terminology, definitions 1
Sets and operations 1
languages 2
Regular Expressions RE 4
Finite Automata FA 5
Deterministic Finite Automaton DFA 5
Non Deterministic Finite Automaton NDFA 8
Language Accepted by Finite Automata 5
Convert Regular Expression into NFA
Constructing regular expression from Finite Automata
Finite Automata with Epsilon moves
Moore and Mealy machines 9
Converting between Moore and Mealy machine
Pumping lemma for regular languages
Kleene's Theorem 7
Regular Grammar 10
Myhill-Nerode Theorem Minimization of DFA
EXAM
Context-free Languages 13
Pushdown Automata 17
CFG/CFL to PDA 18
PDA to CFG/CFL
CFG derivation trees Parsing 22
Chomsky normal form 16
Greibach normal form 16
Ambiguous CFL's
EXAM
TURING MACHINES TM 24
COMPUTABILITY and COMPLEXITY
Unsolvable Problems
Time Complexity
CYK algorithm for CFG's
CFL pumping lemma and properties
Church Turing Thesis
Mustansiriya University – college of sciences – computer science department – second class
, Theory of Computation 3
As a computer IT, you must study the following:
1- Automata and formal language.
Which answers - What are computers (Or what are models of computers)
2- Compatibility.
Which answers - What can be computed by computers?
3- Complexity.
Which answers - What can be efficiently computed?
In automata we will simulates parts of computers. Or we will make mathematical models of computers
Automata are more powerful than any real computer because we can design any machine on papers that can
do everything we want.
Theory of computation is the theoretical study of capabilities and limitations of Computers
(Theoretical models of computation).
Sets
Let A, B, and C be subsets of the universal set U
Distributive properties
A (B U C) (A B) U (A C
A U (B C) (A U B) (A U C
Idempotent properties
A A A,
AUA A.
Double Complement property
(A ) A.
De Morgan’s laws
(A U B) A B
(A B) A UB
Commutative properties
A B B A,
AUB B U A.
Associative laws
A (B C) (A B) C
A U (B U C) (A U B) U C
Identity properties
AU A,
A U A.
Complement properties
AUA U,
A A .
Mustansiriya University – college of sciences – computer science department – second class
