Automata and languages, automat10

Examination

The requirement for the course is a pass on the assignments, the lab assignments, and the written exam. The grade will be the grade obtained at the written exam. You're allowed to bring the course book and own lecture notes taken in class.

Note that you must be registered for the course in order to have the result of your exam reported.

Grading

The exam will be graded based on the intended learning outcomes of the course. After the course, students will be able to (the suggested grades only to be taken as a guideline):

A. Perform basic constructions such as:

• Construct an automaton: 
• for an extensionally defined language; [E] or 
• from a given regular expression; [E]
• Determinize finite automata; [E]
• Check language inclusion (for model checking); [E]
• Minimize finite automata; [E]
• Construct a minimal DFA consistent with a given observation set; [E]
• Construct a context-free grammar for an extensionally defined language; [E]
• Construct a pushdown automaton for a given context-free language; [E]
• Construct a total Turing machine deciding a given problem, [E]
  

B. Formally establish results such as:

• Prove closure properties or relate different models:
• define transformation, [D,C] and then
• prove transformation correct (e.g. language-preserving); [B,A]
• Prove whether a language is or isn't regular or context-free:
• by using the Pumping Lemmas, [D,C] or 
• by using Reduction (i.e. by referring to closure properties); [E]
• Prove that a given context-free grammar generates a given context-free language; [B,A]

C. Interpret and apply fundamental theorems:

• 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]
• Chomsky-Schützenberger Theorem:
• decompose a CFL according to the theorem; [D,C]
• construct a DFA based on the decomposition and the PDA-DFA product construction; [D. C]
• Rice's Theorem:
• argue for undecidability of a given problem. [D, C]

Bonus points will be taken into account, namely one bonus point per homework assignment handed in at the start of the respective class.

Exam resits

Exam resits (sv. omtentor) are by mutual arrangement with the lecturer.

Previous Exams

---