COMP11212 Fundamentals of Computation
Fundamentals of Computation
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP11212 Fundamentals of Computation
Exercise Sheet Exercise 1
Exercises to be submitted in Week 6
Complete the following exercise and submit to Blackboard for marking and feedback. Marks for
these exercises will contribute to your final mark for the unit.
Submit a PDF file with your answers. This could be a scan/photo of hand written exercise or
something typeset using, for example LATEX.
Make sure your work is legible. If we can’t read it, we can’t mark it!
This is an individual assessment and the work should be your own. These exercises are
to help you in your understanding of the materials. Copying others’ solutions will not do that.
Your solution should demonstrate that you have an understanding of the material.
Each exercise is marked using the following scheme. It is possible to get a mark for an exercise
where you haven’t made much, or any, progress, provided your rough work gives evidence that
you have seriously tried it. If you submit just a final answer for an exercise that requires steps in
between you will not get the marks for it.
Attempt Mark
No attempt. 0
Some attempt, but with significant missing parts
or errors.
1
A reasonable attempt showing understanding of
the material, but with some errors or missing
parts.
2
Correct solution showing understanding of the
material. Working or intermediate results are
given where asked for.
3
1 Git Hash: 24e9e39
COMP11212 Fundamentals of Computation – Part I
Exercises
Exercise 1. NFAs
Consider the following NFA.
b
a
a, b
a
b
(a) Which of the following words are accepted by the automaton? , aba, bbb, bab, abab,
babb, bbbb, babb, ababb.
(b) Give a regular expression R such that any words matching R will not be accepted
by the automaton. Give an (informal) explanation of why this is the case.
(c) Convert the NFA into a DFA using the Algorithm shown in the lectures.
Exercise 2. Simulation
Consider the two automata below.
A
X Y
a
b, c
b, c
B
0 1
2
3
a
a
b
c
b, c
b, c
(a) Give a simulation from A to B or provide an argument why a simulation cannot
exist.
(b) Give a simulation from B to A or provide an argument why a simulation cannot
exist.
2 Git Hash: 24e9e39
COMP11212 Fundamentals of Computation – Part I
Exercise 3. Distribution
Proposition (Distributive Law): For expressions p1, p2, p3, any word matching
the regular expression
(p1(p2|p3))
also matches the regular expression
((p1p2)|(p1p3))
Give a proof of the above proposition, or demonstrate that it is false.
Exercise 4. Grammars
(a) Provide a grammar with terminal symbols {a, b} for all non-empty words that start
with ab and end with ab. Show how your grammar generates the strings abab and ababab
and provide an argument as to why it does not generate invalid strings such as baab or
bb.
(b) Provide an unambiguous grammar for the language
{aibjck | i, j, k ∈ N, j ≥ i+ k}.
Justify the non-ambiguity.
Exercise 5. Regular Languages
This exercise relates to languages of words over the alphabet {a, b}.
For a given word w, |wx| is the number of occurences of the character x in the word, i.e. if
w = abaab, then |wa| = 3 and |wb| = 2.
For each the languages below either
(i) give a DFA that recognises the language;
OR
(ii) provide an argument as to why a DFA that recognises the language cannot be produced
(a) All words w s.t. |wa| > |wb|.
(b) All words where the following equality holds: