CS2490 Session 4 - Slides

Definition of Deterministic Finite Automata (DFA)

• Formal definition: Let $\Sigma$ be an alphabet. A deterministic finite automaton (DFA) $A$ over $\Sigma$ is defined by a 5-tuple containing four essential mathematical components:

  • A finite set $Q$: where each element represents the name of a state.

  • An initial state $q_0 \in Q$: the starting state in which all computations begin.

  • A subset $F \subseteq Q$: where each element is an accepting state (also called a final state).

  • A transition function $\delta : \Sigma \times Q \rightarrow Q$: defining the state transition such that when in state $q$ and reading symbol $a$, the automaton transitions to state $\delta(a, q)$.

• DFA Example Structure:

  • Finite set of states: $Q = \{\text{init}, \text{state1}, \text{state2}, \text{trap}\}$

  • Initial state: $q_0 = \text{init}$

  • Set of transitions over alphabet $\Sigma = \{0, 1\}$:

  • $\delta(0, \text{init}) = \text{init}$

  • $\delta(1, \text{init}) = \text{state2}$

  • $\delta(0, \text{state1}) = \text{state2}$

  • $\delta(1, \text{state1}) = \text{init}$

  • $\delta(0, \text{state2}) = \text{state1}$

  • $\delta(1, \text{state2}) = \text{trap}$

  • $\delta(0, \text{trap}) = \text{trap}$

  • $\delta(1, \text{trap}) = \text{trap}$

Computation and Acceptance

• Computation Definition:

  • Let $A = (\Sigma, Q, \delta, q_0, F)$ be a DFA.

  • The computation (or run) of automaton $A$ on an input word $w = w_1 w_2 \dots w_n \in \Sigma^*$ is defined as the sequence of states $s_0, s_1, \dots, s_n \in Q$ satisfying:

  • $s_0 = q_0$

  • $s_i = \delta(w_i, s_{i-1})$ for all $1 \le i \le n$

  • Procedurally, computation means following the sequence of state transitions generated while reading symbols from $w$ sequentially from left to right until reaching the end of the word.

• Acceptance Condition:

  • A computation run is successful when the final state $s_n$ belongs to the accepting set $F$ ($s_n \in F$).

  • When $s_n \in F$, automaton $A$ is said to accept the word $w$.

Step-by-Step Computation Example

• Input string $w = 110110011010110001 \in \{0, 1\}^*$

• Full trace of state transitions step by step:

  • Step 0 (Start): Start in initial state $\text{init}$. Sequence: $\text{init}$

  • Step 1 (Read $1$): $\delta(1, \text{init}) = \text{state2}$. Sequence: $\text{init}, \text{state2}$

  • Step 2 (Read $1$): $\delta(1, \text{state2}) = \text{state1}$. Sequence: $\text{init}, \text{state2}, \text{state1}$

  • Step 3 (Read $0$): $\delta(0, \text{state1}) = \text{state2}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}$

  • Step 4 (Read $1$): $\delta(1, \text{state2}) = \text{state1}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}$

  • Step 5 (Read $1$): $\delta(1, \text{state1}) = \text{init}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}$

  • Step 6 (Read $0$): $\delta(0, \text{init}) = \text{init}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}$

  • Step 7 (Read $0$): $\delta(0, \text{init}) = \text{init}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}$

  • Step 8 (Read $1$): $\delta(1, \text{init}) = \text{state2}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}$

  • Step 9 (Read $1$): $\delta(1, \text{state2}) = \text{state1}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}$

  • Step 10 (Read $0$): $\delta(0, \text{state1}) = \text{state2}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}$

  • Step 11 (Read $1$): $\delta(1, \text{state2}) = \text{state1}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}$

  • Step 12 (Read $0$): $\delta(0, \text{state1}) = \text{state2}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{state2}$

  • Step 13 (Read $1$): $\delta(1, \text{state2}) = \text{state1}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{state2}, \text{state1}$

  • Step 14 (Read $1$): $\delta(1, \text{state1}) = \text{init}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}$

  • Step 15 (Read $0$): $\delta(0, \text{init}) = \text{init}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}$

  • Step 16 (Read $0$): $\delta(0, \text{init}) = \text{init}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}$

  • Step 17 (Read $0$): $\delta(0, \text{init}) = \text{init}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{init}$

  • Step 18 (Read $1$): $\delta(1, \text{init}) = \text{state2}$. Sequence: $\text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{state2}, \text{state1}, \text{init}, \text{init}, \text{init}, \text{init}, \text{state2}$

• Ending state of computation: $\text{state2}$.

Extended Transition Function

• Definition and Intuition:

  • Let $A = (\Sigma, Q, \delta, q_0, F)$ be a DFA, and let $w \in \Sigma^*$ be a word over $\Sigma$.

  • $\delta^*(w, q_0)$ denotes the final state reached at the end of the run of $A$ on input word $w$.

  • Generalizing to any state $q \in Q$, $\delta^*(w, q)$ represents the last state reached in the run of $A$ on word $w$ assuming $q$ were the starting state.

• Inductive Mathematical Definition:

  • The extended transition function $\delta^* : \Sigma^* \times Q \rightarrow Q$ is defined recursively as follows:

  • Base case: $\delta^*(\varepsilon, q) = q$ for all $q \in Q$, where $\varepsilon$ is the empty string.

  • Recursive step: $\delta^*(wa, q) = \delta(a, \delta^*(w, q))$ for all $a \in \Sigma$, $w \in \Sigma^*$, and $q \in Q$

Languages Accepted by DFAs

• Definition of Accepted Language:

  • Let $A = (\Sigma, Q, \delta, q_0, F)$ be a DFA.

  • The language accepted by $A$, denoted $L(A)$, is the formal set of all words accepted by $A$:     $L(A) = \{w \in \Sigma^* \mid \delta^*(w, q_0) \in F\}$

  • Terminology variants: $L(A)$ is also called the language recognized by $A$, or simply the language of $A$

Parity Automaton Example

• Automaton Definition:

  • State Set: $Q = \{\text{even \# of 1's}, \text{odd \# of 1's}\}$

  • Alphabet: $\Sigma = \{0, 1\}$

  • Initial State: $q_0 = \text{even \# of 1's}$

  • Accepting State Set: $F = \{\text{even \# of 1's}\}$

  • Transition Function Rules:

  • $\delta(0, \text{even \# of 1's}) = \text{even \# of 1's}$

  • $\delta(1, \text{even \# of 1's}) = \text{odd \# of 1's}$

  • $\delta(0, \text{odd \# of 1's}) = \text{odd \# of 1's}$

  • $\delta(1, \text{odd \# of 1's}) = \text{even \# of 1's}$

• Target Language Claim:

  • Hypothesis: $L(A) = \{w \in \{0, 1\}^* \mid w \text{ has an even number of 1's}\}$

Rigorous Mathematical Proof for Parity Automaton

• Proof Structure:

  • To prove equality $L(A) = \{w \in \{0, 1\}^* \mid w \text{ has an even number of 1's}\}$, two inclusions must be proven:

  • Direction 1: Every word accepted by $A$ has an even number of $1$'s ($L(A) \subseteq \{w \in \{0, 1\}^* \mid w \text{ has an even number of 1's}\}$).

  • Direction 2: Every word with an even number of $1$'s is accepted by $A$ ($\ authorization {w \in {0, 1}^* \mid w \text{ has an even number of 1's}} \subseteq L(A)).\n- Key Lemma (Inductive Property):\n - Claim: For all n \in \mathbb{N}$, the run of$A$on any word$w$of length$n$ends in the state "$p \text{ # of 1's}$", where$p$is the parity of the number of$1$'s in$w\n - Proof of Key Lemma by Induction on n = |w|:\n - Base Case (n = 0):\n - |w| = 0 \implies w = \varepsilon\n - The count of 1$'s in$\varepsilon$is$0$, which is even ($p = \text{even}).\n - The run on \varepsilon$starts and remains in the initial state$\text{even # of 1's}.\n - Base case holds trivially.\n - Induction Step:\n - Induction Hypothesis: Assume the statement holds for all words of length n \in \mathbb{N}.\n - Let w = w_1 w_2 \dots w_n w_{n+1}$be a word of length$n + 1$.

    • Applying the induction hypothesis to prefix $w_1 \dots w_n$ of length $n$, the run on $w_1 \dots w_n$ ends in state "$p \text{ \# of 1's}$", where $p$ is the parity of the count of $1$'s in $w_1 \dots w_n$

    • The run on $w$ is one step longer than the run on $w_1 \dots w_n$, determined by symbol $w_{n+1}$:

    • If $w_{n+1} = 0$, the ending state remains unchanged ("$p \text{ \# of 1's}$"), and $p$ is also the parity of the number of $1$'s in $w$

    • If $w_{n+1} = 1$, the ending state switches to the opposite state, and the parity of the count of $1$'s in $w$ is the opposite of $p$

    • In both cases, the parity of the total number of $1$'s in $w$ matches the ending state of the run.

• Proof of Direction 1 (Soundness):

  • If $A$ accepts word $w$, then by definition the run of $A$ on $w$ ends in accepting state $\text{even \# of 1's}$.

  • By the key lemma, the parity of the number of $1$'s in $w$ must be even.

• Proof of Direction 2 (Completeness):

  • If word $w$ contains an even number of $1$'s, then by the key lemma, the run of $A$ on $w$ ends in state $\text{even \# of 1's}$.

  • Since $\text{even \# of 1's} \in F$, automaton $A$ accepts $w$

Language Analysis Challenge

• Deterministic Finite Automaton Details:

  • Initial state: $\text{init}$

  • States: $Q = \{\text{init}, \text{state1}, \text{state2}, \text{trap}\}$

  • Transitions:

  • $\delta(0, \text{init}) = \text{init}$, $\delta(1, \text{init}) = \text{state2}$

  • $\delta(0, \text{state1}) = \text{state2}$, $\delta(1, \text{state1}) = \text{init}$

  • $\delta(0, \text{state2}) = \text{state1}$, $\delta(1, \text{state2}) = \text{trap}$

  • $\delta(0, \text{trap}) = \text{trap}$, $\delta(1, \text{trap}) = \text{trap}$

• Language Question:

  • Formally analyze and determine $L(A)$ for this four-state automaton.