Final Exam Topic List

Regular Languages

• Be able to create DFA, NFA and regular expressions.
• Relationship between regular expressions and automata.
• Operations on regular languages.
• Non-regularity.
• Be able to read DFA and NFA diagrams.

Context-Free Languages

• Be able to create CFGs and PDAs.
• Relationship between CFGs and PDAs.
• Relationship between regular languages and context-free languages.
• Be able to read PDA diagrams.
• Be able to interpret context-free languages.

Turing Machines

• Be able to create Turing machine description algorithms.
• Turing machine variants (multi-tape, non-deterministic).
• The Church-Turing Thesis.
• Be able to read TM diagrams.

Computability

• Meaning of decidable and undecidable.
• Meaning of reducibility.
• The Halting problem.

Complexity

• Big-O notation

• Be able to find the Big-O of a function.
• Be able to give the complexity for simple algorithms.
• Definition of $P$, $NP$ and $NP$-complete.
• Be able to show that a problem belongs in $P$ or $NP$.
• The $P$ vs. $NP$-question.

General Things

• The recursion theorem and quines.
• Godel's Incompleteness theorem (roughly what it says).
• The Chomsky hierarchy.
• Given a language, where does it fall in the Chomsky hierarchy?