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

Quiz 3

Nils Anders Danielsson

  1. (1p) Consider the DFA A = ({q₀, q₁}, {1}, δ, q₀, {q₁}), where δ is left unspecified. What is the start state of A?

    1. q₀

    2. q₁

  2. (1p) Consider the DFA A = ({q₀, q₁}, {1}, δ, q₀, {q₁}), where δ is left unspecified. Which accepting states does A have?

    1. None

    2. q₀

    3. q₁

    4. q₀ and q₁

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

      0 1
     → q₀ q₁ q₂
     * q₁ q₂ q₀
    q₂ q₂ q₂

    Denote the DFA’s transition function by δ. What is δ(q₁, 0)?

    1. q₀

    2. q₁

    3. q₂

  4. (1p) Consider the DFA A = ({q₀, q₁}, {1}, δ, q₀, {q₁}), where δ(q₀, 1) = q₁ and δ(q₁, 1) = q₀. Which of the following strings are members of L(A), the language of A?

    1. ε

    2. 1

    3. 11

    4. 111

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

      0 1
     → q₀ q₁ q₂
     * q₁ q₂ q₀
    q₂ q₂ q₂

    Which of the following strings are members of the language of this DFA?

    1. ε

    2. 0

    3. 1

    4. 00

    5. 01

    6. 10

    7. 11