# 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 © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.