General evaluation criteria for 1st middle term exam (3.3. 2005)

Task 1 (Jussi Nuutinen)

Max 16p
a)max 5p
b)max 6p
c)max 5p
Model answers and grading criteria can be foundhere

Task 2 (Marko Tuononen)

Each part 3p. The correct answer 1p. Fully correct justifications were 2 points. If justification was wrong, but the correct idea was known, then 0.5p. If justification nearly correct, just minor error, then 1.5p. If medium error, then 1p. For example, in a, a fully correct Pumping Lemma proof was required for 2 points justification.

Task 3 (Wilhelmiina Hämäläinen)

Each part was 2p. The most common error was that the actual question (why the methods are important?) was not answered, but something else was explained. 1p for halfly correct answer (or if something useful was mentioned) and 2 p for fully correct answer.
a) Nondeterministic automaton is hard and not at all sensible to implement. If it is implemented (all possible transition paths have to be checked) the time requirement is in the worst case O(k^n), where k is the number of states and n is length of the input string.
Notice that determinization does not make the automaton smaller, but generally larger!
b) Minimization makes automaton smaller and thus it is much easier to implement and it becomes slightly more efficient (in switch-sentence we have less cases to check).
c) A regular exprssion can be transformed to corresponding automaton mechanically i.e. we can implement the transforming program. This is the core of many search engines and e.g. grep-command.
d) Pumping Lemma can be used to show that the language is non-regular and thus more powerful tools are needed. We don't waste time in trying to find automaton solution.