Course
| code | CS311 |
| credit_hours | 3 |
| title | Theory of Computation |
| arbic title | |
| prequisites | CS202 |
| credit hours | 3 |
| Description/Outcomes | This course introduces the fundamental mathematical models of computation. The course presents both inherent capabilities and limitations of these computational models as well as their relationships with formal languages. Topics to be covered include: Finite automata and regular languages, deterministic and nondeterministic computations, pumping lemma for regular languages, context-free grammars and languages, pushdown automata, pumping lemma for context-free languages, and Turing machines and their variants. |
| arabic Description/Outcomes | |
| objectives | 1. Understand the capabilities and limitationof computational models.
2. Prove whether or not a given languageis regular.
3. Prove whether or not a given languag is context-free.
4. Design variants of Turing machines.
5. Understand the relationship between the regular, context-free and recursively enumerable languages.
6. Implement simple parsers using Finite State Automata and regular expressions. |
| arabic objectives | |
| ref. books | John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley. |
| arabic ref. books | |
| textbook | Michael Sipser, Introduction to the Theory of Computation, Cengage Learning. |
| arabic textbook | |
| objective set | |
| content set | |
| course file |
530_CS311_CS311.pdf |