Finite automata and formal languages (DIT322, TMV028), 2019/2020

Quiz 4

Nils Anders Danielsson

  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₀}

    Denote the NFA’s transition function by δ. What states, if any, are members of the set δ(q₀, 0)?

    1. q₀

    2. q₁

    3. q₂

  2. (1p) Consider the NFA of the previous exercise again. What states, if any, are members of δhat(q₀, 011) (where δhat is the transition function for strings)?

    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