past_exam_04-solutions only

(a) Give a derivation of aaabbccdd from G . Which of the strings aaabbbbcccdd and aabbdddccc are derivable from G ? Briefly explain your answer (but there is no need to give full derivations). Answer: S ⇒ AB ⇒ aAB ⇒ aaAB ⇒ aaaAB ⇒ aaaB ⇒ aaabB ⇒ aaabbB ⇒ aaabbC ⇒ aaabbcCd ⇒ aaabbccCdd ⇒ aaabbccdd aaabbbbcccdd is not derivable as it has an unequal number of c ’s and d ’s. aabbdddccc is not derivable, as to have d ’s before the c ’s we need to use D , but the rules for D do not result in any finite derivation. (b) Describe informally and in set notation the language of G . Answer: { a i b j c k d k | i, j, k ≥ 0 } . This is the language containing any number of a ’s followed by any number of b ’s followed by any number of c ’s followed by the same number of d ’s. (c) Describe how the language of G changes if the rule S → SC is added to G . Compare this change to the one in which the rule B → BC is added to G (but S → SC is not). There is no need to write out the set notation for the new languages. Answer: If the rule S → SC is added, this means that we can now have any number of repetitions of the groups of equal numbers of c ’s and d ’s, so that abccddcdcccdddcdcdcd is now derivable. If the rule B → BC is added, then this has the same effect (ie both rule additions result in the same new strings being derivable). 4. Grammars (8+2+2 = 12 marks) Consider the informal specification of a language below. • All Fine Dining programs commence with table(id) where id is an identifier, and conclude with pour , which may be optionally followed by tips , thanks or both. • Apart from the above constructs a Fine Dining program consists of an entree section , a main section , a dessert section , a cheese section and a coffee section , in that order. Only the main section is compulsory; all of the others are optional. • An entree section commences with starters , ends with sretrats and contains zero or more variable declarations. • A main section optionally commences with plate and concludes with napkin and contains at least one gourmet dish . • A gourmet dish is one of – steak – chicken – fish – lentils – while boolean expression repeat gourmet dish stop – doggy bag gourmet dish bag(identifier) • A dessert section begins with sweets , ends with smile and contains one or two of the following keywords (repeats allowed): ice cream mousse pancakes fruit salad creme brulee smarties • A cheese section commences with mouse , optionally ends with esuom and contains exactly three of the following keywords (repeats allowed): cheddar edam camembert brie swiss gorgonzola parmesan ricotta blue optionally followed by a single statement of the form repeat dessert section and cheese section until boolean expression • A coffee section begins with drinks , ends with satisfaction and contains exactly one of the following keywords: cappuccino devonshire tea 3

hello99,n34s1n1n11,hbf02,bsfsbsfb11111111111111111 n1s2e3w4 goodbye03,superman04,rocky99,w43243434s21212,n4s2 but the following should not. he9329219292 ww1111111111111 Answer: 6. Chomsky hierarchy (5+4+3+3 = 15 marks) (a) Prove that there is no DFA for the language L 1 = { a i b i c i | i ≥ 0 } . Answer: Assume that L 1 is regular. Hence there is a DFA M which accepts L 1 . Let the number of states in M be k . Then by the Pumping Lemma for any w ∈ L 1 for which | w | ≥ k there exist x, y, z such that w = xyz , y = λ , | xy | ≤ k and xy i z ∈ L 1 ∀ i ≥ 0. Let w = a k b k c k . As | w | > k , the Pumping Lemma applies and so we have xyz = a k b k c k . As | xy | ≤ k , y must contain only a ’s and so y = a m for some 1 ≤ m ≤ k . Now consider xy 2 z = a k + m b k c k , and so xy 2 z ∈ L 1 , which is a contradiction. Hence L 1 is not regular. (b) Give a context-free grammar for the language L 2 = { a i b j c k | i = j, i, j, k ≥ 0 } Answer: S → AC | BC A → aAb | aA | a B → aBb | Bb | b C → cC | λ (c) Give an example of a string w ∈ a * b * c * for which w ∈ L 1 and w ∈ L 2 . Answer: aabbccc (d) Explain how your proof that L 1 is not regular would need to be adapted in order to show that L 2 is not regular. (Hint: consider how you could show that w ∈ L 2 ). Answer: To show that a string of the form a i b j c k is not in L 1 , we only need to show that either i = j , as in the proof above, or j = k . To show that a string of the form a i b j c k is not in L 2 , we need to show that i = j . Hence the proof would have to be adapted to show that xy 2 z = a k + m b j c i ∈ L 2 , i.e. that k + m = j . By choosing w to be a k b k + m c k , this can be achieved. 7. Pushdown automata (3+4+3 = 10 marks) Consider the pushdown automaton M below. Q = { q 0 , q 1 , q 2 } δ ( q 0 , a, λ = { ( q 0 , A ) } δ ( q 1 , a, A ) = { ( q 2 , λ ) } Σ = { a, b, c } δ ( q 0 , b, λ = { ( q 0 , B ) } δ ( q 2 , b, A ) = { ( q 2 , λ ) } Γ = { A, B } δ ( q 0 , b, B ) = { ( q 1 , λ ) } F = { q 2 } δ ( q 1 , a, B ) = { ( q 1 , λ ) } (a) Trace the execution of M with inputs aabbbaab , aabbabbb and aaabbaab . Answer: ( q 0 , aabbbaab, λ ) ( q 0 , abbbaab, A ) ( q 0 , bbbaab, AA ) ( q 0 , bbaab, BAA ) 6

over-write the input string during computation if you wish). Hence BBBBBBBBB 1 and B 0000000 B 1 are also correct. Similarly, for the initial tape contents B 10101111 B and B 0011 B , correct outputs include B 10101111 B 0 and B 0011 B 1 respectively. You may use any notation for Turing machines and any variety of Turing machine that you wish. Note that you may also use other characters in the tape alphabet if you wish. Answer: End of exam paper 9