DD2371 Automata Theory
======================

Constructions:

1. Construct an automaton:
   from an informally described language; [E] or
   from a given regular expression; [E]

2. Determinize and minimize automata; [E]

3. Construct a pushdown automaton for a given context-free language; [E]

4. Construct a total Turing machine deciding a given problem, [E]


Formally establish results:

5. Prove closure properties or relate different models:
   define transformation, [D,C] and then
   prove transformation correct (e.g. language-preserving); [B,A]

6. Prove whether a language is or isn't regular or context-free:
   by using the Pumping Lemmata, [D,C] or 
   by using Reduction (i.e. referring to closure properties); [E]

7. Prove that a given context-free grammar generates a given
   context-free language; [B,A]
   
8. Prove undecidability of a given problem:
   by reducing from a known undecidable problem; [B,A] or
   by referring to Rice's Theorem; [D,C]


Interpret and apply fundamental theorems:

9. Myhill-Nerode Theorem:
   form equivalence classes w.r.t. a language; [D,C] 
   prove lower bounds for number of DFA states for a language; [B,A]

10. Chomsky-Schützenberger:
    decompose a CFL according to the theorem; [D,C]