Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP11212 Fundamentals of Computation

Coursework Sheet 1

Summative exercises to be submitted in Week 06

Complete the following exercises and submit to Blackboard by the above deadline 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.

Exercise 1.   NFAs

Consider the following NFA.

(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.   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 3.   Simulation

Consider the two automata below.

A

B

(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.

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

1. give a DFA that recognises the language;

OR

2. 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:

|wa| mod 2 = |wb| mod 2