############## The following hints are only intended as either hints or as a quick check that you are on the right track. The answers do not correspond to actual exam answers. They may be updated during the exam grading. ############## 1a: Yes, we only need to count if the length of the string is divisible by 3. 1b: No, it's not transitive. 1c: Yes. There are many possible Turing machines. To get points you need to give a pointer of how the Turing machine would compute this (high-level explanation sufficient). As a useful subroutine you could e.g. describe a Turing machine that for a sequence of n 0's produces a string with 2n 0's. How many times should you repeat this? 1d: For k = 0 the answer is yes. For any k > 0 the answer is no (the simplest argument is that LR(1) equals deterministic context-free languages, which are stronger than regular languages, that can already define all finite languages). The intended answer is "no", but a well motivated k = 0 answer did also give a point (but then you have to specify that k = 0, since that specific claim is not true for arbitrary k). 2 There is no single correct answer here (in principle) but it's easiest to argue that regular languages are a good fit. Checking strings can be done with regular expressions, which we know can be evaluated efficiently (by converting to NFA, and then DFA). If you argue that a stronger class of languages is required (e.g., CF, or TM-recognizable) then you should motivate why the weaker languages are not sufficient. A formal proof that the language is regular is not needed, but some kind of motivation is needed. During the grading we decided to bump up the number of points of this exercise to 2. 3a E(1) = {1,3} is the starting state. State a b ----- {1,3} {2,3} {2,3} {2,3} {1,2,3,4} {2,3} {1,2,3,4} {1,2,3,4} {2,3} The last one is the accept state since it contains 4. 3b: All non-empty strings over {a,b}. 4a If we do it mechanically we obtain a table like the following. | (q_i) | (q_rip}) | (q_j) | (R_1R_2^*R_3+R_4) | Simplified | | ----- | ---------------- | ----- | ----------------------------- | ----------- | | (q_s) | (A) | (B) | (\vareps ilon,b^*,a) | (b^*a) | | (q_s) | (A) | (q_f) | (\varepsilon,b^*,\varepsilon) | (b^*) | | (B) | (A) | (q_f) | (b,b^*,\varepsilon) | (bb^*) | | (B) | (A) | ( B) | (b,b^*,a + b) | (bb^*a+b) | | (C) | (A) | (B) | ((a+b)b^*a) | ((a+b)b^*a) | | (C) | (A) | (q_f) | ((a+b)b^*,\varepsilon) | ((a+b)b^*) | 4b: the "given automaton" here refers to the original DFA. Removing inacessible states in a DFA does not change its language, so this simplification is correct. If you have interpreted "this automaton" as a GNFA, and answered that we cannot remove the start state, this is not quite complete, since the start state by definition is always reachable. 5: See tutorial 6, exercise 4a, for a similar exercise. We can e.g. choose the string s = a^p b^{p+1} c^{p+2}. We assume an arbitary partitioning s=uvxyz and then observe that vxy cannot span all three symbols. We pump up or down depending on the symbols (if we do not have any c's, it's OK to pump up, but if we instead have no a's, pumping up is not guaranteed to work). 6: use the construction from the lecture (systematic construction of a PDA when the grammar is in GNF, each production rule gives you a new entry in the transition function). Manually constructing a PDA from scratch is much harder. 7a: Use the tool that August sent to the course list. The problematic state should be I2. 7b: Bottom up LR parse sequence (we write S for shift, and R for reduce, . and - are the two symbols in the alphabet): Step Action 1 S - 2 R S -> - 3 S - 4 R S -> - 5 S . 6 R S -> . 7 S . 8 R S -> . 9 R L -> S 10 R L -> SL 11 R L -> SL 12 R L -> SL 13 Accept (L' -> L) This gives the tree: L' (13) | L (12) /\ / \ / \ S (2) \ | \ - \ L (11) /\ / \ / \ / \ S (4) \ | \ _ \ L (10) /\ / \ / \ / \ S (6) \ | \ . \ L(9) | S (8) | . 8: the language is undecidable. A sufficient "high-level" explanation is that it's undecidable, since in order to detect the condition we would need to simulate the given TM on input 0 and input 1, and we have no way of detecting if this is going to loop or not. One can give a mapping reduction from e.g. the string acceptance problem. If we spell out the conditions needed in the mapping reduction we see that we for need to produce such that M accepts w <===> M' accepts 0 and M' does not accept 1. We can easily make sure that M' always rejects 1. Then, on input 0, M' should accept iff M accepts w. The mapping reduction should thus (given ) produce a TM M' of the following form: +-----------------------------------------+ | M' | | | input tape | +-------------------------+ accept | accept -------------> | | Simulate M on w |---------------> | | (if input = 0) |reject | reject | +-------------------------+---------------> | | | if input != 0: reject | +-----------------------------------------+