syllabus of computation theory

This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church s Thesis, undesirability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems.


In particular, students will be able to:

1. Memorize the Introductory to the Computational theory and Automata Languages.
2. Describe the basics of Set Notation.
3. Understanding the operations in set theory.
4. Convert and system model to the BNF- Notation and to the Syntax Chart
5. develop the Equivalent Grammar, Type of Grammars, Context Sensitive Grammar
6. Determine the Context Free Grammar, Useless Symbols
7. Design models in Chomsky Normal Form CNF
8. Design models in Greibach Normal Form GNF
9. Remember Regular Grammars LEFT, RIGHT linear