CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan, TA: Xiao Ke.
PROBLEM SET 11 SOLUTIONS

  1. We'll draw state table for the finite-state automata.

    (a).
    The state table of the finite state automaton is following

    tabular12

    where   tex2html_wrap_inline84   is the start state, and it's a NDFM.

    (b).
    The state table of the finite state automaton is following

    tabular17

    where   tex2html_wrap_inline84   is the start state.

    (c).
    The state table of the finite state automaton is following

    tabular22

    where   tex2html_wrap_inline84   is the start state.

  2. (a).
    For the first machine, the output is  1 .
    For the second machine, the output is  0000 .
    For the third machine, the output is  0000 .

    (b).
    For first machine, the output is  001 .
    For the second machine, the output is  1000001 .
    For the third machine, the output is  11011011 .

    (c).
    For the first machine, the output is  1 .
    For the second machine, the output is  00000000000 .
    For the third machine, the output is  00010101010 .

  3. Assume the alphabet for this finite state machine is   tex2html_wrap_inline172  . And the states is   tex2html_wrap_inline174  , while   tex2html_wrap_inline84   is the start state,   tex2html_wrap_inline178   expresses the state of having balance  5i  cents, and the   tex2html_wrap_inline182   is the final state. We will draw the state tables for it.

    tabular30

  4. Label the states with the ordered pairs (i,j), i=0,1, j=0,1,2, where i is the number of zeros mod 2 and j is the number of ones mod 3. (0,0) is the start state, and (0,0), (1,0), (1,1), and (1,2) are the final states. The state table is as follows.

    tabular35

  5. Lets draw the state table for FSM.

    tabular40

    where   tex2html_wrap_inline84   is the start state, and   tex2html_wrap_inline310   is the final state.

  6. The language for the first machine is   tex2html_wrap_inline312  .
    The language for the second machine is   tex2html_wrap_inline314  .
    The language for the third machine is   tex2html_wrap_inline316  .

  7. Has appeared in Problem set 10.

  8. Has appeared in Problem set 10

  9. Has appeared in Problem set 10.

  10. Has appeared in Problem set 10.

  11. Has appeared in Problem set 10.