This course introduces the mathematical foundations of all computation. Core concepts of automata, formal languages, grammar, decidability and computability will be discussed. Topics include: Basic notions: string, prefix, suffix, substring, concatenation; Cardinality; Distinction between uncountable and countable infinite; Different proof techniques: proof by construction, proof by contradiction, pigeon hole principle; Deterministic and non-deterministic finite state automata; Regular language, regular expression; Equivalence of NFA and DFA; Pumping Lemma, non regular languages; Context free grammar (CFG) and push down automata (PDA; Chomsky normal form; Parsing; Turing machine, Universal Turing machine and Halting problem; Goedel numbering; P/NP complexity. Students taking this course should possess a strong background in discrete mathematics and data structures.

Course Type | Major |
---|---|

Credit Hour | 3 |

Lecture Hour | 45 |

- Defineand describe formal models of computation, such as finite automata, pushdown automata, and Turing machines.
- demonstrate their the understanding of key notions, such as algorithm, computability, decidability, and complexity through problem solving.
- Convert between finite automata, regular grammars, and regular expression representations of regular languages.
- Apply the pumping lemma for regular languages to determine if a language is regular.
- Convert between grammars and push-down automata for context-free languages.
- Applylearned concepts to create proofs regarding the computational complexity of various problems.

*Elements of the Theory of Computation (2nd Edition)*by H. Lewis, C. Papadimitriou*Introduction to the Theory of Computation*by M. Sipser*Introduction to Automata Theory, Languages & Computation (3rd Edition)*by J. Hopcroft, R. Motwani, J. Ullman

Biweekly Quiz, One Midterm Exam, One Final Exam, Project

Letter Grade | Marks | Grade Point |
---|---|---|

A | 90 - 100 | 4.00 |

A- | 85 - 89 | 3.70 |

B+ | 80 - 84 | 3.30 |

B | 75 - 79 | 3.00 |

B- | 70 - 74 | 2.70 |

C+ | 65 - 69 | 2.30 |

C | 60 - 64 | 2.00 |

C- | 55 - 59 | 1.70 |

D+ | 50 - 54 | 1.30 |

D | 45 - 49 | 1.00 |

F | 00 - 44 | 0.00 |