Finite automata theory and formal languages (DIT321, TMV027), 2018/2019

Quiz 4

Nils Anders Danielsson

If you cannot access Canvas and submit your answers via email, please only give the answers (a number or a list of numbers), and no motivating arguments.

  1. (1p) Consider the NFA that is given by the following transition table:

      0 1
     → q₀ {q₀, q₂} {q₀, q₁}
     * q₁ ∅ {q₂}
    q₂ {q₂} {q₀}

    If the NFA is in state q₀ and the next input symbol is 0, what states (if any) is the NFA in after processing this symbol?

    1. q₀

    2. q₁

    3. q₂

  2. (1p) Consider the NFA of the previous exercise again. If the NFA is in state q₀, what states (if any) is the NFA in after processing the string 011?

    1. q₀

    2. q₁

    3. q₂

  3. (1p) Consider the NFA of the first exercise again. Which of the following strings (if any) are in the language of this NFA?

    1. ε

    2. 0

    3. 1

    4. 00

    5. 01

    6. 10

    7. 11

  4. (1p) Consider the NFA that is given by the following transition table:

      0 1
     → q₀ {q₁, q₃} ∅
    q₁ ∅ {q₀, q₂}
     * q₂ ∅ {q₀, q₂}
    q₃ {q₀, q₄} ∅
     * q₄ {q₀, q₄} ∅

    Which of the following strings (if any) are in the language of this NFA?

    1. 010

    2. 01100

    3. 0001

    4. 00010

  5. (1p) Consider the NFA of the first exercise again. Apply the subset construction to this NFA and remove all inaccessible states. Which of the DFAs below is equal, up to renaming of states, to the DFA that is obtained?

    1.   0 1
       → A A B
       * B A B
    2.   0 1
       → A C B
       * B C B
      C C B
    3.   0 1
       → A C B
       * B C D
      C C B
       * D C D