(Note: this lab was done as a class-wide guided exercise. The problems here may not be exactly the same as the ones presented live in class.)

Problem 1: Automata to Symbols

Consider the following finite automata diagram over alphabet \(\Sigma = \set{0, 1}\).

      ┌────1─────┐
      ↓          │
──> (q0) ──1──> (q1)
    │  ↑        │  ↑
    0  0        0  0
    ↓  │        ↓  │
    (q3) ──1──> [q4]
      ↑          │
      └────1─────┘

q0 is the initial state and q4, denoted with square brackets, is the sole accepting state.

1. Give a formal description of this automata.
2. Give two strings \(s_1\) and \(s_2\), the first of which is accepted by the automata and the second of which is rejected by the automata.

Problem 2: Symbols to Automata

Consider the following formal definition of a finite automata: \(D = (Q, q_0, \Sigma, \delta, F)\) where:

• \(Q = \set{q_0, q_1, q_2}\),
• \(\Sigma = \set{0, 1}\), and
• \(F = \set{q_2}\).

\(\delta\) is a function defined by cases as follows:

\[\begin{align*} \delta(q_0, 0) =&\; q_0 \\ \delta(q_0, 1) =&\; q_1 \\ \delta(q_1, 0) =&\; q_0 \\ \delta(q_1, 1) =&\; q_2 \\ \delta(q_1, 0) =&\; q_0 \\ \delta(q_1, 1) =&\; q_0 \\ \end{align*}\]

Draw an automata diagram that captures this formal definition. Explore how the automata operates and in a sentence, describe the set of strings that the automata accepts.

Problem 3: Design

1. Design a finite automata that recognizes the set of binary strings, i.e., strings drawn from \(\Sigma^* = \{\, 0, 1 \,\}\), that have an even number of \(0\)s. Note that zero \(0\)s is an even number of \(0\)s!