- p. 596 - 3, 5, 7
- p. 608 - 1, 3, 7, 21, 23 (No because (f, c) edge)
- p. 618 - 1, 3, 5, 7, 11, 35
f(u1) → v1
f(u2) → v3
f(u5) → v4
f(u4) → v2
f(u3) → v5u1 u2 u3 u4 u5 u1 1 1 u2 1 1 u3 1 1 u4 1 1 u5 1 1 v1 v3 v5 v2 v4 v1 1 1 v3 1 1 v5 1 1 v2 1 1 v4 1 1 - p. 629 - 1, 5, 11, 21, 29
Isomorphic, corresponding paths:
- u1, u2, u7, u6, u5, u4, u3, u8, u1
- v1, v2, v3, v4, v5, v8, v7, v6, v1
- p. 643 - 3, 19 (b-=3, b+=1), 31, 37
- p. 655 - 3
procedure Dijkstra( c, d, G : weighted connected simple graphs with all weights positive ) G has a path from a to z and weights w[vi,vj]=∞ if edge (vi,vj) does not exist
for i := 1 to n L[vi] := ∞
L[ a ] := 0
S := ∅while z ∉ S
u := vertex not in S with L[u] minimal
S := S U {u}
for all vertices v not in S
if L[u] + w[u, v] < L[v] then L[v] := L[u] + w[u, v]
At the end of the for, L[v] is minimal from L[u] for all v
w a b c d e f g z a ∞ 4 3 ∞ ∞ ∞ ∞ ∞ b 4 ∞ 2 5 ∞ ∞ ∞ ∞ c 3 2 ∞ 3 6 ∞ ∞ ∞ d ∞ 5 3 ∞ 1 5 ∞ ∞ e ∞ ∞ 6 1 ∞ ∞ 5 ∞ f ∞ ∞ ∞ 5 ∞ ∞ 2 7 g ∞ ∞ ∞ ∞ 5 2 ∞ 4 z ∞ ∞ ∞ ∞ ∞ 7 4 ∞ w[vi, vj]
L a 0 b 4 c 3 d 6 e 97f 11 g 12 z 16 S
acbdefgz Find shortest path from a to z.
Give final values for L and S.
Path: acdegz
length: 5
Cost: 16
- p. 693 - 1, 3
- p. 708 - 1, 3
- p. 722 - 7, 13, 15, 17 (start at bottom of tree with highest precedence operation), 24a (ans. 32), b (ans. 40), c (ans. 32)
- p. 735 - 13, 14 (HW10), 16 for #13
Algorithm 1 Depth-First Search procedure DFS( G : connected graph, vertices: v1, v2,...vn)
T := tree consisting of v1
visit( v1 )procedure visit( v : vertex of G) -- visit alphabetically
for each vertex w adjacent to v and not yet in T
add vertex w and edge (v, w) to T
visit( w )
13. Start with a 
Algorithm 2 Breadth-First Search procedure BFS( G : graph, vertices: v1,v2,...vn)
T := tree consisting of v1L := empty list
put v1 in the list L of unprocessed vertices
while L is not empty
remove the first vertex, v, from L
for each neighbor w of v (alphabetically)
if w not in L and not in T then
add w to the end of list L
add w and edge (v, w) to T
16 #13 Start with a 
Queue L
- a
- bc
- c
- d
- ef
- fh
- hg
- gi
- ij
- j
- p. 756 - 3, 5, 13
- p. 757 - Example 1
F(x,y,z) = xyz The sum of one product.
G(x,y,z) = xyz + xyz The sum of two products.
- P. 765 - 3, 5, 6ab (HW11)
3.
5.
- p. 794 - 3, 5a, 5b, 23, 24 (HW12)
3. sentence
/ \
noun phrase intransitive verb phrase
/ \ / \
article noun intransitive verb adverb
| | | |
the hare runsthesleepytortoiseP = { S → 1A, S → 0A, A → 0B, B → 1A, B → 1}
5a. 10101
S
|
1A
\
0B
\
1A
\
0B
\
1
5b. 10110S
|
1A
\
0B
\
1A
\
fails24.
P = {S → abS, S → bcS, S → bbS, S → a, S → cb}
bcbba
- S
|
bcS
|
bbS
|
a
bbcbba
- S
|
bbS
|
bcS
|
bbS
|
a
bcabbbbbcb
- S
|
bcS
|
abS
|
bbS
|
bbS
|
cb
- S
- p. 797 - Figure 1 (Table 1)
- Show the states that the Finite State Machine (FSM) traverses on the input listed below
- Show the output of the FSM on the same input
- Input: 5 cents, 10 cents, 25 cents, 5 cents, orange button
- p. 802 - 1, 3
- p. 814 - 1, 9, 11, 17, 23
11. Which of these strings is recognized by the finite-state automaton below?
- 111
- 0011
- 1010111
- 011011011
17. What language is recognized?
0 U 1(0 U 1)(0 U 1)*
23. Construct a deterministic finite-state automaton that recognizes the the set of strings starting with 01.
- p. 826
3. Determine whether 0101 belongs to each of the regular sets.
- 01*0*
- 0(11)*(01)*
- 0(10)*1*
- 0*10(0 U 1)
- (01)*(11)*
- 0*(10 U 11)*
- 0*(10)*11
- 01(01 U 0)1*
5. Express each of these sets using a regular expression.
- 0, 11, 010
- three 0's followed by two or more 0's
- strings of odd length
- strings that contain exactly one 1
- strings not containing 000 and ending in 1
0 U 11 U 110
00000*
(0 U 1)(00 U 01 U 10 U 11)*
0*10*
(1 U 01 U 001)*14b (HW12) Construct a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar:
G = (V, T, S, P}
T = { 0, 1 }
V = { 0, 1, S, A, B}
P = { S → λ, S → 1A, S → 0, A → 1A, A → 0B, B → 1B, B → 1}Dark states are final.
Production Input Transition S → λ λ ss S → 1A 1 ss to sA S → 0 0 ss to sF A → 1A 1 sA to sA A → 0B 0 sA to sB B → 1B 1 sB to sB B → 1 1 sB to sF 