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?

Copyright © 2024 Ian Finlayson | Licensed under a Creative Commons BY-NC-SA 4.0 License.