iConnect

Results

Science - Course - Theory of Computation

More in this section
  • Course Code: CMPS346
  • Credits: 3
  • Hours Distribution: (3Crs.:2 Lec,2 Tut)
  • Course Type: Major Core (MJC)

Course Description

This course is an introduction to the fundamental models of computation used throughout computer science. Topics include deterministic finite automata (DFA), regular languages, non-deterministic finite automata (NFA), equivalence of NFAs and DFAs, closure properties, regular expressions, the pumping lemma, pushdown automata, context free languages, context free grammar, ambiguity, Chomsky normal form, Turing machines, decidability, the halting problem and topics related to time complexity, P, NP and NP-Completeness. Pre-req.: CMPS 248.