173205 Theoretical foundations of computer science 2nd middle term exam 21.4. 2005
Write your name, student number, signature, course name and date to all solution papers. Total 42 p.
1. (10 p) Let’s consider the following grammarG:
S→AC|CaX|CaCb|CcC|c|DE|CaA|a|CbY|CbCc
X→ACb
Y →ECc
A→CaX|CaCb
C→CcC|c D→CaD|a E→CbY|CbCc
Ca →a Cb→b Cc →c
Study with CYK-algorithm, whether stringaabbcbelongs to the language described by the grammar!
2. (12 p) The main subclasses of context-free languages are:
Linear languages LL(1)-languages
Deterministic languages Unambiguous languages
Inherently abmiguous languages
(a) Into which subclass of context-free languages do the following languages belong? Se- lect the easiest (innermost) subclass, into which the language belongs. Notice that you can transform the language to a more familiar form, if you want.
• G1:S →SD|D,D→0|1|...|9
• G2:S →aXbC|AbY c,X →aXb|²,C→cC|c,A→aA|a,Y →bY c|²
• G3:S →aSb|B,B→bB|²
(b) How can you solve the parsing problem ”x∈L?” most efficiently in each of the sub- classes?
3. (10 p) Construct a standard-model deterministic Turing machine, which adds number 2 to the input binary number. You can assume that the input is given the least significant bit on left (e.g. number 4 is presented as 001).
4. (10 p)
(a) According to Rice’s theorem all nontrivial semantic properties of Turing machines are unsolvable. What does this exactly mean?
(b) Which of the following properties of Turing machines are syntactic and which seman- tic?
• Machine accepts all stringsx∈ {a, b}∗,|x|<100.
• For the codecM of machineM holds|cM|<100.
• In the machine there are at least 5 states, from which you can enter the accepting final state.
• If the size of input isn, then the machine performs exactlynsteps before entering the final state.
(c) Consider the nontrivial semantic properties in the previous task. Are they partially solvable or totally unsolvable? Justify carefully!
