I. DFA 5-Tuple Definition

• A Deterministic Finite Automaton is a 5-tuple: M = ( Q, Σ, δ, q_start, F ).
• M denotes the Machine (aka the DFA). Alternatively, we can use D to denote the DFA.

A. Components

1. Q — States

• A finite set of states.

2. Σ — Alphabet

• A finite set of input symbols.
• Note: 𝜖 is not a member of alphabet Σ; it never can be because 𝜖 is always a string. And alphabet Σ is always a set of symbols, not strings.
  • Remember, alphabet Σ contains symbols only. Σ^* contains strings only.

3. δ — Transition Function

• The transition function is defined: δ: Q × Σ → Q.
• In JH handwritten notes (Notebook #2) esp. Section 6.2, I often denote this same function as:
  • MOVE( set of input states, symbol we are seeking to match )
  • MOVE( q, a )
• This means that given a current state q ∈ Q; and an input symbol a ∈ Σ; the DFA moves to exactly one next state δ(q,a) ∈ Q.
• In this context, “deterministic” means that for each pair (q,a), there is exactly one next state.
  • When drawing DFAs, we often omit transitions that go to a dead/sink state.
  • This can make diagrams look sparse (fewer outgoing arrows shown), even though δ is total: for every q ∈ Q and every a ∈ Σ, the function δ( q, a) is defined.

4. q_start — Start State

• The very first state we initialize the DFA with. q₀ is a synonym of q_start.
• q_start ∈ Q.

5. F — Accepting (aka Final) States

• A set of accepting (final) states.
• The set F is a subset of Q: F ⊆ Q.

B. Acceptance

1. A DFA reads an input string w ∈ Σ^* symbol-by-symbol.
2. Formally, textbooks define the extended transition function:

• δ^*: Q × Σ^* → Q where:
  • δ^*(q, 𝜖) = q
  • δ^*(q, x⋅a ) = δ( δ^*(q,x), a ) where x ∈ Σ^* and a ∈ Σ
    • x⋅a means “x concatenated with a”; it is not multiplication.

3. Acceptance test: A DFA M accepts w iff δ^*( q₀, w ) ∈ F.

II. NFA 5-Tuple Definition

• A Non-deterministic Finite Automaton is a 5-tuple: M = ( Q, Σ, δ, q_start, F ).
• M denotes the Machine (aka the NFA). Alternatively, we can use N to denote the NFA.

A. Components

1. Q — States

• A finite set of states.
• NFA version is the same as for DFA.

2. Σ — Alphabet

• A finite set of input symbols.
• NFA version is the same as for DFA.

3. δ — Transition Function

• 3.1 NFA without 𝜖-transitions. The function is defined as:

  • δ: Q × Σ → P(Q)
  • Where P(Q) is the power set of Q (aka the set of all subsets of Q).
  • In other words, given a current state q ∈ Q and an input symbol a ∈ Σ, the NFA can move to a set of next states δ(q,a) ⊆ Q.
    • This set of outbound arrows can be empty (aka no valid transition); or it can contain multiple states (nondeterminism).

• 3.2 NFA with 𝜖-transitions. The function is defined as:

  • δ: Q × ( Σ ∪ {𝜖} ) → P(Q)
  • i.e., the set of outbound arrows includes both moves labelledy by symbols from the alphabet Σ as well as “free moves” via 𝜖-transitions.

4. q_start — Start State

• The very first state we initialize the DFA with. q₀ is a synonym of q_start.
• NFA version is the same as for DFA.

5. F — Accepting (aka Final) States

• A set of accepting (final) states.
• The set F is a subset of Q: F ⊆ Q.
• NFA version is the same as for DFA.

B. Acceptance

1. An NFA reads an input string w ∈ Σ^*, symbol by symbol (aka “letter by letter”).
2. Because an NFA can be in multiple states at once, the extended transition concept returns a set of possible states.
3. NFA (with no 𝜖-transitions)
   • Define the extended transition function:
     • δ^*: Q × Σ^* → P(Q) where:
       • δ^*(q, 𝜖) = {q}
       • δ^*(q, x ⋅ a) = {q}
4. NFA (with 𝜖-transitions)