Summary
Summary COS3701 STUDY NOTES
- Course
- Institution
Summary of 57 pages for the course COS3701 - Theoretical Computer Science III at University of South Africa (COS3701 STUDY NOTES)
[Show more]
Seller
Follow
stuviaevans7
Content preview
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: hassan.kassim@yahoo.com
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller stuviaevans7. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.79. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
85169 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now