# haskell辅导 | COMP30026 Models of Computation

用HasKell实现计算模型

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 = {a

ibaj

| 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 applying 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

1 1

ǫ, 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 reversesorted, 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,

Pn

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 submission 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 description 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 appropriate 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