CS计算机代考程序代写 Finite State Automaton CPS 420 W2017 MIDTERM 2 SOLUTIONS 1

CPS 420 W2017 MIDTERM 2 SOLUTIONS 1
PART
1.
A – GRAPH THEORY – 20 MARKS
Matrices in Graph Theory (10 marks)
This question is based on the following graph G:
0
2
3
1
a)
Fill out the adjacency matrix for the graph G: 0123
0 1 2 3
Fill out the following matrix A which is defined as follows:
A(i,j) = number of walks of length 2 from vertex i to vertex j in the graph G.
0123
0 1 2 3
This can be derived by squaring the adjacency matrix.
0
1
0
2
1
0
1
0
1
0
0
0
0
0
1
0
b)
1
0
3
0
1
1
0
2
0
1
0
2
1
0
0
0

CPS 420 W2017 MIDTERM 2 SOLUTIONS 2
2. Circuits (6 marks)
This question is based on the following graph G (the edge numbers are edge names):
A
1
D5
B8 27
C
9 6
10 G
E
34 F
H
a) Give an Euler circuit for G (listing the vertices and edges as they are traversed) or explain why this cannot be done.
Starting at A, there are 8 Euler circuits as each of the cycles ADF,DG, GEBCH can be traversed either clockwise or counter clockwise. The one that is fully clockwise is: A2D5G6E7B8C9H10G4D3F1A
b) Give a Hamiltonian circuit for G (listing the vertices and edges as they are traversed) or explain why this cannot be done.
This graph consists of 3 simple circuits: ADF, DG, GEBCH with are connected at vertices D and G. Any circuit for the entire graph (i.e. including all the vertices) will need to traverse both D and G more than twice in order to include both the ADF and the GEBCH circuits. Therefore none of the circuits which include all the vertices will be Hanmiltonian circuits. .
3. Minimum Spanning Tree (4 marks)
For the weighted graph G underneath, where the edge numbers are weights:
A
1
D
B 57
8
C
F 93
5
6
1 J
E
24 GHI1
10
Draw a minimum spanning tree (draw the edges you are keeping with their weights).
A
1
D
B
7
9 6
8
C
F
1 J
E
24 GHI1

CPS 420 W2017 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 Σ={a,b}: L1 = {a, aa, ab}
L2 = {b, bb, ab}
a)
{ b)
{ c)
{
d) {
2.
List all the elements of L1  L2
ab }
List all the elements of L1  L2
a, aa, ab, b, bb }
List all the elements of L1  L2
(a,b), (a,bb), (a,ab), (aa,b), (aa,bb), (aa,ab), (ab,b), (ab,bb), (ab,ab)
List all the elements of L1 L2
ab, abb, aab, aabb, aaab, abbb, abab
Regular Expression (10 marks)
}
}
 An integer can be in base ten (decimal), base sixteen (hex) of base eight (octal).
 A decimal integer is either the single digit 0 or a sequence of one or more digits between
0 and 9 such that the leading digit is not a 0.
 A hex number starts with the string “0x” which is then followed by one or more digits
between 0 and 9 or letters between A and F.
 An octal number starts with the single digit 0 which is then followed by one or more
digits between 0 and 7.
You do not need to simplify your regular expression
(0 | [1-9][0-9]*) | (0x [0-9,A-F]+) | (0 [0-7]+)
Write a regular expression to match all integers in a new programming language. Integers are defined as follows:

CPS 420 W2017 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
0,1 10
Regular expression
1 (0|1)* 0
(a (ba)*) | (b (ab)*)
a b
b a
a b
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)*abc(b|c)*
a,b
a
b,c
bc
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)*abc(b|c)*
b
b,c
a
ba
bc
a