CPS 420 W2018 MIDTERM 2 SOLUTIONS 1
PART
1.
A – GRAPH THEORY – 20 MARKS
Graph of a Relation (4 marks)
Draw the directed graph of the following relation R in the set of vertices S={0,1,2,3,4,5}
x,yS xRy iff x mod 3 < y mod 3
1 02
53
4
2.
Circuits (6 marks)
This question is based on the following graph G (the edge numbers are edge names):
A1B2C3D
E5F G8
H 14 I J K
a) Starting at vertex A, give an Euler circuit for G (listing the vertices and edges as
they are traversed) or explain why this cannot be done
The graph has no Euler circuit because verticess E and G have odd degrees.
b) Starting at vertex A, give a Hamiltonian circuit for G (listing the vertices and edges as they are traversed) or explain why this cannot be done.
A1B2C3D8K13G12J11F10I14H9E4A
CPS 420 W2018 MIDTERM 2 SOLUTIONS 2
3. Connectedness and Complements (10 marks)
This question is based on the following graph G:
F
A
E
B
D
C
a) List all the connected components of G. Each connected component should be described as the set of all the vertices in the connected component.
G has 3 connected components: {C}, {D}, and {A,B,E,F}
b) Draw the complement Gc of the graph G
F
A
E
B
D
C
c) Using the same format as in a) list all the connected components of Gc Gc has one connected component: {A, B, C, D, E, F}
CPS 420 W2018 MIDTERM 2 SOLUTIONS 3
PART B – REGULAR EXPRESSIONS AND FINITE STATE AUTOMATA – 40 MARKS 1. Operations on Languages (10 marks)
Define the following two languages of the alphabet Σ={0,1,2}: L1 = {0, 01, 02}
L2 = {, 2, 02}
2.
a) List all the elements of L1 L2
{ 02 }
b) List all the elements of L1 L2
{ 0, 01, 02, , 2 }
c) List all the elements of L1 L2
{ (0,), (0,2), (0,02), (01,), (01,2), (01,02), (02,), (02,2), (02,02) }
d) List all the elements of L1 L2
{ 0, 02, 002, 01, 012, 0102, 022, 0202 }
Regular Expression (10 marks)
Write a regular expression to match all sets in a new programming language. Sets are strings like “{}”, “{740}”, “{hello,799,0,55,friend}” and they are defined as follows:
A set is a list of zero of more entries surrounded by curly parentheses.
If the list contains more than 1 entry, the entries are separated by commas.
An entry is either a name or an integer
A name is a string of 1 or more lower-case letter (i.e. a to z)
An integer is either the digit 0 or a string of one or more digits which does not start with
the digit 0
You do not need to simplify your regular expression
{ | ( 0 | [1-9][0-9]* | [a-z]+ ) ( , ( 0 | [1-9][0-9]* | [a-z]+ ) )* } (matching parentheses are shown in colour to improve legibility.)
CPS 420 W2018 MIDTERM 2 SOLUTIONS 4
3.
Finite State Automata (20 Marks)
a) Give a regular expression for each of the following finite state automata. Make these regular expressions as simple as possible.
Automaton
Regular expression
(a|b) (b | a+b)*
(0|1) (0* | 1*)
a,b
0,1
0,1
ba a
b
0
1
In the next two questions the simplest possible automaton refers to an automaton with as few states as possible.
b) Draw the simplest possible NFA (non-deterministic finite state automaton) on an input alphabet I={a,b,c} which recognizes the following regular expression: (a|b)(a|c)*(b|c)
a,c
a,b
b,c
c) Draw the simplest possible DFA (deterministic finite state automaton) on an input alphabet I={a,b,c} which recognizes the following regular expression: (a|b)(a|c)*(b|c). Your DFA should handle all possible inputs
a
c
a,b
c a
a,b,c
cbb a,b,c