Review for Chapters 9-12:

• On-Line 9-12 Quizzes
• Activities, includes the answers.
• HW9-12 solutions

Chapter 9-12 questions

• Chapter 9
  • 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, 36

    

    

       

    

    f(u1) → v1 f(u2) → v3 f(u5) → v4 f(u4) → v2 f(u3) → v5

    u1 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

    

    No u vertex of degree 4 as is v₂

     

  • p. 629 - 1, 5, 11, 21, 29

    

    Isomorphic, corresponding paths:

    • u₁, u₂, u₇, u₆, u₅, u₄, u₃, u₈, u₁
    • v₁, v₂, v₃, v₄, v₅, v₈, v₇, v₆, v₁

• p. 643 - 3, 19 (b^-=3, b⁺=1), 31, 37

No Euler circuit.

Euler path: a, e, c, e, b, e, d, b, a, c, d

Neither

b^-=3, b⁺=1    must enter b 3 times but can only exit 1 time.

31. Hamilton circuit: a, b, c, d, e, a

Hamilton path: a, b, c, f, d, e

 

• 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 97 f 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

• Chapter 10
  • 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)

  

  

  

  

+     /     \   +        /  /  \     /  \ x   *   x    y     /  \   x     y

+          /     \         x       /                /  \              +    y             /  \           *     x          /  \         x    y

b)  ++x*xy/xy        +x/+*xyxy

c)   xxy*+xy/+        xxy*x+y/+

d)   (x+x*y)+(x/y)    x+(x*y+x)/y 

 

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 v1   L := 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

   

• Chapter 11
  • p. 756 - 3, 5

  

   

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

    

• Chapter 12
  • p. 794 - 3, 5a, 5b, 23, 24 (HW12)

          Not complete. Ooops!
  

  3.        sentence
             /            \
   noun phrase    intransitive verb phrase
     /           \               /                         \
  article     noun    intransitive verb      adverb
    |              |            |                             |
  the          hare       runs         the        sleepy      tortoise    

   

  

   

  P = { S → 0A, S → 1A, A → 0B, B → 1A, B → 1}

  5a.           10101

                      S
                      |
                    1A
                       \
                       0B
                          \
                          1A
                             \
                             0B
                                \
                                 1
  
  5b.            10110

                      S
                      |
                    1A
                       \
                       0B
                          \
                          1A
                             \
                            fails

  

  24.

          P = {S → abS, S → bcS, S → bbS, S → a, S → cb}

                  bcbba

  1.                     S
                         |
                       bcS
                           |
                         bbS
                             |
                             a
     
     
                     bbcbba
      
  2.                     S
                         |
                       bbS
                           |
                         bcS
                             |
                           bbS
                               |
                               a
     
         P = {S → abS, S → bcS, S → bbS, S → a, S → cb}
     
                     bcabbbbbcb
      
  3.                     S
                         |
                       bcS
                           |
                         abS
                             |
                           bbS
                               |
                             bbS
                                 |
                                cb

  
             

  • 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?

   

  1. 111                  
  2. 0011                  
  3. 1010111           
  4. 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.

    1. 01*0*
    2. 0(11)*(01)*
    3. 0(10)*1*
    4. 0*10(0 U 1)
    5. (01)*(11)*
    6. 0*(10 U 11)*
    7. 0*(10)*11
    8. 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