 | First Term, Academic Year 2020/2021 M 416 - Theory of computation | Helwan University Faculty of science Math. Department |
Course Description
This module introduces the theory of computation through a set of abstract machines that serve as models for computation - finite automata, pushdown automata, and Turing machines – and examines the relationship between these automata and formal languages. Additional topics beyond the automata classes themselves include deterministic and nondeterministic machines, regular expressions, context free grammars, undecidability, and the P = NP question.
Course Objectives:
Finite automata are useful models for many important kinds of hardware and software. Here are the most important kinds: Software for designing and checking the behavior of digital circuits; The “lexical analyzer” of a typical complier, that is, the compiler component that breaks the input text into logical units, such as identifiers, keywords, and punctuation; Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases, or other patterns; Software for verifying systems of all types that have a finite number of distinct states, such as communication protocols or protocols for secure exchange of information.
Course Components
1. Basic concepts and definitions; Set operations; partition of a set
2. Equivalence relations; Properties on relation on set.
3. Proving Equivalences about Sets.
4. Central concepts of Automata Theory.
5. Regular Expressions; Operations on Regular expressions
6. Finite Automata and Regular Expressions.
7. Conversion from FA and regular expressions.
8. Deterministic Finite Automata (DFA); Minimization of DFA.
9. Non-Deterministic Finite Automata (NDFA).
10. Equivalence of Deterministic and Non-Deterministic Finite Automata.
11. Equivalence between DFA,NFA, NFA-Λ
12. Context-Free Grammars.
13. Parse Trees; Ambiguity in Grammars and Languages.
14. Standard Forms; Chomsky Normal Forms;
15. Greibach normal Forms.
16. Minimization of CFG’s.
17. Pushdown Automata (PDA).
18. Deterministic and Non-Deterministic (PDA); Formal definition of NPDA.
19. Transition functions of NPDA; NPDA Execution.
20. Accepting Strings with NPDA; Equivalence of PDAs and CFG.
21. The Turing Machine.
22. Programming Techniques for Turing Machines; Formal definition of TM’s.
23. TM’s as acceptors; TM’s as transducers; Recognizing Languages with TM’s.; Sorting with
24. TM’s.; Programming in TM’s.
25. Multiple Tracks, Subroutines, Complexity issues and analysis
Text book:
Title: Introduction to Computer Theory
Author: Daniel I. A. Cohen
Publisher: Prentice-Hall, Second Edition, 1997.
In addition to the above, the students will be provided with handouts by the lecturer.
Recommended:
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Second Edition, Prentice-Hall, 2001
Learning Outcomes:
Knowledge and understanding
- Acquire a full understanding and mentality of Automata Theory as the basis of all computer science
languages design
- Have a clear understanding of the Automata theory concepts such as RE's, DFA's, NFA's, Stack's,
Turing machines, and Grammars
Cognitive skills (thinking and analysis).
- Be able to design FAs, NFAs, Grammars, languages modelling, small compilers basics
- Be able to design sample automata
Communication skills (personal and academic).
- Be able to minimize FA's and Grammars of Context Free Languages
Practical and subject specific skills (Transferable Skills).
Evaluation Method:
Method | Percentage |
Quizzes & Assignments | 10% |
Projects | 10% |
Mid Test | 10% |
Final Examination | 70% |
Course Topics
Week | Basic and support material to be covered | Slides | Homework |
(1) | Basic concepts and definitions Set operations; partition of a set Equivalence relations; Properties on relation on set; Proving Equivalences about Sets. Central concepts of Automata Theory. |
| |
(2) | Regular Expressions; Operations on Regular expressions Finite Automata and Regular Expressions. Recursive definitions; Conversion from FA and regular expressions; Kleen’s Theory; Mealy Moore Machines. Conversion from Mealy to Moore and vice versa. | ||
(3) | Deterministic Finite Automata (DFA). Minimization of DFA; Non-Deterministic Finite Automata (NDFA). |
| |
(4) | Equivalence of Deterministic and Non- Deterministic Finite Automata. | ||
(5) | Finite Automata with Epsilon-Transition. Equivalence between DFA,NFA, NFA-Λ | Lecture 3b | Assignment 1 |
(6) | Pumping Lemma for Regular Languages. Closure Properties of Regular Languages. | Lecture 4 | Sheet 3 |
(7) | Context-Free Grammars; Regular Grammars; Parse Trees. | Lecture 5 |
|
(8) | Ambiguity in Grammars and Languages. Standard Forms; Chomsky Normal Forms; Greibach normal Forms. | Lecture 6 | Sheet 4 |
(9) | Pumping Lemma for Context-Free Languages; Closure Properties of Context-Free Languages; Minimization of CFG’s. | Lecture 7 |
|
(10) | Pushdown Automata (PDA). | Lecture 8 | Sheet 5 |
(11) | Deterministic and Non-Deterministic (PDA); Formal definition of NPDA. Transition functions of NPDA; NPDA Execution; Accepting Strings with NPDA; Equivalence of PDAs and CFG. | Lecture 9 |
|
(12) | The Turing Machine. | Lecture 10 | Sheet 6 |
(13) | Programming Techniques for Turing Machines; Formal definition of TM’s. TM’s as acceptors; TM’s as transducers; Recognizing Languages with TM’s.; Sorting with TM’s.; Programming in TM’s | Lecture 11 |
|
(14) | Multiple Tracks, Subroutines, Complexity issues and analysis | Lecture 12 | Sheet 7 |
(15) Specimen examination (Optional) | Equivalence of PDA’s and CFG. | Lecture 13 |
|
(16) Final Examination | Revision |
|
|
No comments:
Post a Comment