- May 15, 2020

The University of Melbourne School of Computing and Information Systems COMP30026 Models of Computation Assignment 2, 2019 Released: 27 September. Deadline: 21 October at 23:00 Purpose To improve and consolidate your understanding of functions, relations, regular languages, context-free languages, finite-state automata and push-down automata. To develop skills in analysis and formal reasoning about complex concepts, including proof by induction. To practise putting rigorous arguments in writing. Challenge 1 Give context-free grammars for these languages: a. The set A of odd-length strings in {a, b}∗ whose first, middle and last symbols are all the same. For example, b and ababa are in A, but ǫ, aaaa, and abbbb are not. b. The set B = {aibaj | i 6= j}. For example, ab and abaaa are in B, but ǫ, a, b, and aabaa are not. Challenge 2 Consider the language C = { w ∈ {a, b}∗ | w contains at least as many as as bs } For example, ǫ, aaa, aba, and bbaababaa are all in C, but bbb and bbaaabb are not. a. Construct a 3-state push-down automaton to recognise C. Provide the solution as a transition diagram. Partial marks are given for a C recogniser with more than 3 states. b. Prove formally that the following context-free grammar G generates C: S → ǫ | a | a S b | b S a | S S Hint: Proceed in two steps; prove that every string in L(G) is in C (by structural induction) and prove that every string in C is in L(G) (by induction on the length of the string). Note: For this challenge we have designed the marking scheme so that you can get away with solving just one of 2(a) and 2(b) if you want. Each of 2(a) and 2(b) is marked to a maximum of 2, and if you submit both, your mark for Challenge 2 will be the maximum of your marks for the two sub-challenges. Challenge 3 Consider the two language-transformer functions triple and snip defined as follows: triple(L) = {www | w ∈ L} snip(L) = {xz | xyz ∈ L and |x| = |y| = |z|} Note that snip(L) discards a string w from L unless w has length 3k for some k ∈ N (possibly 0), and then the strings whose lengths are multiples of 3 have their middle thirds removed. For example, if L = {ab, bab, bbb, babba, aabbaa} then snip(L) = {bb, aaaa}. a. Let R be a regular language. Is R3 = R ◦ R ◦ R necessarily regular? Justify your answer. b. Let R be a regular language. Is triple(R) necessarily regular? Justify your answer. c. Let R be a regular language. Show that snip(R) is not necessarily regular. Challenge 4 This challenge is to be answered on Grok. See the last page for submission instructions. Let ≤ be a partial order on the set S. We say that a function h : S → S is: • idempotent (Idem) iff ∀x ∈ S (h(h(x)) = h(x)) • isotone (Iso) iff ∀x, y ∈ S (x ≤ y⇒ h(x) ≤ h(y)) • a closure operator iff it is idempotent and isotone • increasing (Inc) iff ∀x ∈ S (x ≤ h(x)) • an upper closure operator (UCO) iff it is a closure operator and increasing Closure operators are important and appear in many different contexts. We have met several; for example, when we take the transitive closure of a relation, we are really ap- plying an upper closure operator to the relation. Here is an example of a upper closure operator on (P(Z),⊆), that is, the set of integer sets (ordered by the subset ordering): addEvens(S) = S ∪ {n ∈ Z | n is even} Namely, (1) it is idempotent: addEvens always produces a set which includes all even integers, and when applied to such a set, addEvens is just the identity function; (2) it is isotone: if S ⊆ S ′ then addEvens(S) ⊆ addEvens(S ′); and (3) it is increasing: addEvens(S) is always a superset of S. Consider T = {a, b, c, d} and the relation ≤ on T , defined by x ≤ y iff x = a ∨ x = y ∨ y = d. The Hasse diagram for T is shown on the right. There are 256 functions in T → T . The table below the Hasse diagram lists 10 of these functions. For example, f3 is the mapping {a 7→ b, b 7→ d, c 7→ a, d 7→ c}. On Grok, define 10 lists f0 . . . f9, such that the list fi gives those properties (a selection of Idem, Iso, Inc, and UCO) that fi possesses (and only those properties). Grok defines a suitable Haskell type for this. For example, for the function g : T → T defined by g(t) = c, the list of properties would be g = [Idem,Iso]. a b c d a b c d f0 a a a a f1 a a a b f2 a b c d f3 b d a c f4 b d d d f5 c c c d f6 c d c d f7 d b b d f8 d b c a f9 d b c d Challenge 5 q1 q2 q3 q4 q5 0,1 11 ǫ, 0 1 1 0 This challenge is to design a regular expression and three DFAs, and submit them via Grok. See the last page for submission instructions. a. An NFA N is shown on the right. Give a regular expression for L(N), the language recognised by N . The expression should use only the regular operations, that is, union, concatenation, and Kleene star (apart from ǫ, 0, and 1). Now let the alphabet Σ = {1, 2, 3}. Design DFAs to recognise these three regular languages: b. The set P of reverse-sorted strings. By “reverse-sorted” we mean: No 1 comes before any 2 or 3, and no 2 comes before any 3. For example, ǫ, 2, and 33111 are reverse- sorted, but 321211 is not. c. The set Q of strings, the sum of whose elements is divisible by 4. That is, Q = { a1a2 · · · an ∣ ∣ n ≥ 0, ∑n i=1 ai = 4k, for some k ∈ N } For example, ǫ, 31, 3333, and 11111112111 are all in Q (because each string of digits adds up to some multiple of 4), but 2, 311, 333, and 1111111211 are not in Q. d. The set R = P \Q, of strings that are in P but not in Q. Challenge 6 This challenge is to design a Haskell function that generates certain DFAs. It should be solved on Grok. In Lecture 14 we went through the exercise of constructing a DFA that could recognise a certain subset of {0, 1}∗, namely the set of binary strings that represent natural numbers that are multiples of 5 (call that language M5). For example, ǫ, 000, 101, 00101101, and 1100100 were all elements of M5 and accepted by the DFA, whereas 11, 0110, 101110, and 1100111 were not members, and were all rejected. We now want to generalise that idea. Write a Haskell function multiples :: Int -> DFA so that ‘multiples n’ (n > 0) produces a DFA (with alphabet {0, 1}) that recognises the language Mn of binary strings representing natural numbers that are multiples of n. We will use the following marking scheme for Challenge 6: • +0.5 marks if the function works (produces a correct DFA) for 1 ≤ n ≤ 6. • +0.5 marks if the function produces minimal DFAs for the cases 1 ≤ n ≤ 6. • +0.5 marks if the function works for any n. • +0.5 marks if the function always produces a minimal DFA, for any n. We suggest you work in stages: 1. First think through and hand-code the solutions for 1 ≤ n ≤ 6. 2. Then think about minimising these 6 DFAs, by hand (no need to program anything, so far). 3. The first stage should help you discover the general pattern of the problem, leading to a general solution for all n. 4. The second stage might help you find the general pattern for minimal DFAs, leading to an enhanced general solution. Submission and assessment All challenges should be solved and submitted by students individually. Your solution will count for 12 marks out of 100 for the subject. Each challenge is worth 2 marks. Marks are primarily allocated for correctness, but elegance and how clearly you communicate your thinking will also be taken into account. Some of the challenges are harder than others, and that is a deliberate design. For example, you may find 3c harder than 3a and 3b, and the last 0.5 marks for Challenge 6 may require more work than the rest of that challenge. The deadline is 21 October at 23:00. Late submission will be possible, but a late sub- mission penalty will apply: a flagfall of 1 mark, and then 1 mark per 12 hours late. For challenges 1–3, submit a PDF document via the LMS. This document should be no more than 2 MB in size. If you produce an MS Word document, it must be exported and submitted as PDF, and satisfy the space limit of 2 MB. We also accept neat hand-written submissions, but these must be scanned and provided as PDF, and again, they must respect the size limit. If you scan your document, make sure you set the resolution so that the generated document is no more than 2 MB. The assignment submission site on the LMS explains what you can do if you find it hard to satisfy this space requirement. For challenges 4–6, submit on Grok. The required format for submitted solutions will be clear when you open the Grok modules, but briefly, for Challenge 4 you define ten Haskell lists of type [FunctionProperty], where the inhabitants of FunctionProperty are Idem, Iso, Inc, and UCO. For Challenge 5 you use the Haskell representations for DFAs and regular expressions introduced in Worksheets 3 and 4, and for Challenge 6, you will need to write some Haskell code. To submit, you need to click “mark”. The feedback you will receive at submission time is limited to well-formedness checking; the correctness of your solutions is something you will need to test and be confident about. You can submit as many times as you like. What gets marked is the last submission you made before the deadline. Once again, for those who want to use the assignment to get some LATEX practice, the source of this document will be available in the LMS, in the content area where you find the PDF version. Make sure that you have enough time towards the end of the assignment to present your solutions carefully. A nice presentation is sometimes more time consuming than solving the problems. Start early; note that time you put in early usually turns out more productive than a last-minute effort. Individual work is expected, but if you get stuck, email Matt or Harald a precise descrip- tion of the problem, bring up the problem at the lecture, or (our preferred option) use the LMS discussion board. The COMP30026 LMS discussion forum is both useful and appro- priate for this; soliciting help from sources other than the above will be considered cheating and will lead to disciplinary action. Harald and Matt 27 September 2019