Evaluation criteria
The default is that all who have really tried to solve the problem get
2 points. If your solution is extra good, you get 3 points (you should have
reached the underlying goals or something even better). If the report is
just a sketch (e.g. you haven't answered all questions) it is 1 point
(or even 0 point, if there is no trial at all).
To get 3 points the report should contain:
In problem 0
- some solution to code special characters, e.g. their
ascii numbers or new user defined Morse codes
- recognition that binary codes are just binary numbers
and Morse alphabet is based on binary signals
- all symbolic (written) languages can be coded by Morse alphabet
(binary alphabet) <-> such languages can be managed by the digital computer
- also good point: coding in binary alphabet increases the length of
the message enormously: if we have to code n characters, each
character needs log n bits (2-based logarithm <- with k bits you can
code 2^k different strings of equal length)
In problem 1
- recognition that there are (uncountable number of) problems which are
totally unsolvable
- some problems which are so time consuming that they are
unsolvable in practice
- we have to describe the problems in some formal way to be able to
compare and analyze them (it's not sensible to try to really solve them
for that)
- some trial to classify problems by their
difficultiness, e.g. reductions to known problems (database of
"prototype problems" of different levels) or reference to Chomsky hierarchy
Also good points:
- Chomsky hierarcy gives some outlines, how
"difficult" the problem is, and we can use reductions to known
problems in some classes (or outside classes to show that something
is unsolvable)
- time and space requirements can also be studied by reductions to some
problems in a known requirement class (e.g. NP-complete problems)
- some problems are compuational by their nature ("humanistic" problems)
- for some problems there may exist only approximative solutions
- sometimes division into subproblems helps: if a subproblem is unsolvable,
the whole problem is as well
Problem 2
- some solution for both problems with regular expressions (or other
notation, which is capable of describing the patterns)
- the solution of b) doesn't have to handle all possible situations
(e.g. user defined types) - just the basic expression for function
definitions like in the example
- same method works with all pattern matching problems
Also good point: if we allow arbitrary number of paranthesis in the
definition, the regular expressions can't describe them!
Problem 3
- transition diagram, which describes the functions of the coffee machine,
without any further restrictions (the notation of finite automata was not
demanded, if your own notation caught the same)
- pseudocode algorithm, which descibes the functions - simplest way is a
loop with switch statement as given in the lecture material
Problem 4
- transition diagram of the nondeterministic automaton, which
describes the functions of the text editor (N.B. Don't confuse
states and transitions!)
- the equivalent deterministic automaton
- some interpretation: now the states hide the nondeterminism ("error or ok"-
states)
Problem 5
- basic idea:
1) construct automata from the correct solution and students' solutions
2) minimize the automata: the result of minimization is unique
3) compare the automata
- how the automaton is constructed from the given regular expression?
Problem 6
1) Without quotation marks the rhyme language is regular. Let's denote:
t=The story begun
Now we can give a regular expression (t:)^* t (at least once the sentence,
but can be repeated as many times as wanted)
2) With quotation marks nonregular: the problem is that we should have
equal number of beginning quotation marks and end quotation marks, and
finite automata cannot count them.
(t:'')^k t ('')^k
So in fact of form a^k t b^k, which looks very familiar...
Everybopdy who even tried to solve the nonregularity with the Pumping Lemma
got 3 points.
Problem 7
- Everybody, who returned a report with idea description and a correct
grammar and represented the masterpiece in the Art Exhibition got 6
points.
- If the idea report was returned with a proper grammar, but not
implemented, it was 2 points.
- If both the report (+ grammar) and the program were returned, but not
demonstrated in the Art Exhibition, then it was 4 points.
- If you had some trial in initial report, but not concerning grammars,
you got 1p.
Problem 8
A pushdown automaton (represented as a diagram or transition table)
was required. N.B. You need different stack symbols for each
parantheses type.
How to program: you can use a stack as in the automaton (i.e. push a
parantheses/special character into stack, when you meet a beginning
paranthesis, and pop a character, when you meet an end
parantheses. Compare if they correspond each other.
Problem 9
The solution can be found
here
The parser program seemed to be so difficult that we gave 3 points, if
you just had the correct (LL(1)-form) grammar and some trial to make a
recursive parser for it. N.B. The grammar was essential! You were asked not to
use any stack, but program the grammar.
N.B. If you just returned a program without any grammar or own report,
it was 0 points. Just printing existing solutions from the net doesn't
teach you anything... If you look at example, try even to understand,
what it does and why - so you can modify it for your needs.
Problem 10
Total 6 points required:
- the idea of CYK algorithm represented (how it really works)
- tested with example strings (one of them belongs and the other doesn't
into language)
- how to transform a context-free grammar into CNF (idea of all phases of
transformation)
-> then all context-free languages can be parsed with CYK
Problem 11
For 3 points:
- general idea of three tape summing machine (not only for some example
strings): either as transition diagram, transition table or very careful
description by words (also described, what to do, when end symbol is met)
* carry bit can be remembered by moving to some state or
* it can be written into third tape and summed with new digits of operand
strings
- if just the transitions, then the idea also described by words or simulated
by examples
- answer to question, can it be performed by 1-tape machine (if it was
described carefully, it could compensate minor faults)
- if only the idea by words or by simulating the tape with example strings,
then 2 points, if correct
one
solution
Problem 12
For 3 points:
- transition diagrams of all functions + some description by words
- if only two of them done, then 2 points
- good ideas for other "library functions" and how to "call functions"
could compensate the faults ("call" can be just transition to that
diagram from the "program" diagram, although some of you had even
thought, how universal machine could do that, if the transition
functions are as code on the tape)
- some good "library function" ideas: empty tape, length of the string,
replace uppercases by downcases or vice versa, got to beginning, go to end,
change two substrings, search a substring,...
some solutions
Problem 13
For 3 points:
- all Turing machines can be coded as binary numbers (idea)
- now another TM can study the behaviour of other TM's with some input
- we can construct a TM (variation of universal TM), which simulates other
TM's and checks if they print letter 'a'
- problem: if the other TM doesn't halt, our simulation doesn't halt either
-> partially solvable (so unsolvable) problem
- for perfect solution also a proof that we cannot study that property by
any means (counter argument method) would have been needed, but now 3 points
were given if the unsolvability was justified otherwise carefully
Problem 14
This was a philosophical problem, so there isn't only one correct
answer. All well justified considerations, which showed that you had
understood the meaning of results gave 3 points. Also processing by
means of art could give total 3 points alone, if they demonstrated deep
understanding.
Your solutions were really good and it would be nice to put them somewhere
into net, if you send the files (html, pdf, ps) to me!