Assignment 2 Deterministic Finite Automata

CSC2047 – Assessment: Individual Coursework 2

Question Sheet
Total Marks: 100

1. Answer all the following questions on Deterministic Finite Automata (DFA).
a. Describe, in English, the language recognised by the DFA illustrated in the following
finite state machine.
[5 marks]
b. Illustrate the following DFA using a finite state machine, given the definition
𝑀 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹) where
𝑄 = {𝑆, 𝑞1𝑞2𝑞3
}
Σ = {𝑎, 𝑏}
𝛿:𝑄 × Σ → 𝑄 is defined by the transition diagram:
𝑸 \ 𝚺 𝒂 𝒃
𝒔 𝑠 𝑞1
𝒒𝟏 𝑞2 𝑞3
𝒒𝟐 𝑠 𝑞1
𝒒𝟑 𝑞2 𝑞3
𝑞0: 𝑠
𝐹 = {𝑞3
}
[5 marks]
c. Design a DFA to recognise the language consisting of all binary strings which start
with the pattern 11 and end with 00. [You only need to illustrate the DFA, you do
not need to formally define the DFA with a 5-tuple].
[10 marks]
2. Answer the following questions related to Nondeterministic Finite Automata (NFA)
a. Describe, in English, the language of the following NFA
[5 marks]
𝑞0 𝑞1 𝑞2 𝑞3 𝑞4
0
0
0
0
1 0,1
1
1
1
𝑞0 𝑞1 𝑞2
𝜖
0 1
CSC2047 – Assessment: Individual Coursework 2
b. Convert the NFA in 2a) into a DFA which recognises the same language.
[It is not mandatory to give the details of the construction process of the DFA.
However, it is recommended that you do show working out in case you make
some mistake in which case partial marks can be awarded for showing the correct
process.]
[10 marks]
c. Give a regular expression to describe the language of the NFA in 2a).
[It is not mandatory to give the details of the process used to deduce the regular
expression. However, it is recommended that you do show working out in case
you make some mistake in which case partial marks can be awarded for showing
the correct process.]
[5 marks]
d. Design a NFA to recognise the language consisting of all strings, over the
alphabet {𝑎, 𝑏, 𝑐}, that do not end with the pattern 𝑏𝑏𝑐.
[10 marks]
3. Answer the following questions related to regular expressions.
a. For each of the following languages over the alphabet Σ = {𝑥𝑦𝑧}, give two strings
that are members of the language.
i. (𝑥𝑦)
∗
ii. 𝑦
∗ ∪ 𝑧𝑥
+
iii. Σ𝑥Σ𝑦Σ𝑧
iv. 𝑦
∗
𝑧
∗𝑥
2
v. (𝑥 ∪ 𝑦)𝑧
∗
[5 marks]
b. Illustrate the NFA which recognises the language 𝑦
∗ ∪ 𝑧𝑥
+ using a finite state
machine.
[5 marks]
c. Write a regular expression for the following languages over the alphabet {𝑥, 𝑦, 𝑧}.
i. The set of all strings where any and all instances of 𝑥 and 𝑦 appear before
any and all instances of 𝑧 (For example, this would contain strings such as
𝑥𝑦, 𝑦𝑥, 𝑥𝑦𝑧𝑧, 𝑥𝑥𝑦𝑦𝑦𝑧𝑧, 𝑦𝑥𝑦𝑦𝑥𝑧𝑧𝑧 to name a few).
[10 marks]
ii. The set of all strings with exactly 2 𝑦′s appearing anywhere in the string.
[10 marks]
4. Decide whether or not the following language, over the alphabet {𝑎, 𝑏, 𝑐} is regular. If so,
design a DFA/NFA to recognise it, and if not, give a formal proof (based on the Pumping
Lemma).
a. {𝑤| 𝑤 in (𝑎
𝑘 ∪ 𝑏
𝑘
) for 𝑘 ≥ 0}
[10 marks]
b. {𝑎
𝑖𝑏
𝑗
𝑐
2𝑖+2𝑗
|𝑖,𝑗, 𝑘 ≥ 0}
[10 marks]