Course
code CS311
credit_hours 3
title Theory of Computation
arbic title
prequisites CS202
credit hours 3
Describtion/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 Describtion/Outcomes
objectives Upon completion of this course, students should be able to:
1. Understand the capabilities and limitation of computational models.
2. Prove whether or not a given language is regular.
3. Prove whether or not a given language 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 Michael Sipser, Introduction to the Theory of Computation, 2nd Edition, Course technology, 2006.
arabic ref. books
textbook Hopcroft J, Introduction To Automata Theory, Languages, And Computation, 3rd Edition, Pearson, 2009.
arabic textbook
objective set combined
content set bullets
Course Content
content serial describtion