Finite Automata, Part 2

I. 5-Tuple Definition of DFAs

• A DFA (Deterministic Finite Automaton) is a 5-tuple: M = ( Q, Σ, δ, q₀, F ).
• M denotes the Machine (aka 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.
• 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 State

• The very first state we initialize the FA with.
• q₀ ∈ 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.

Ignore registers below

“ap = Upper case sigma aka Alphabet Σ “sp = Sigma Star (Uppercase Sigma with Asterisk) Σ^* “lp = lowercase delta δ “kp = lowercase delta STAR italicized δ^* “ep = lowercase epsilon aka the empty string 𝜖 “bp = subset of; ⊆ “up = Union symbol ∪ “zp = empty set symbol ∅ “dp = dot product symbol ⋅ “np = NOT equal sign ≠ “xp = vanilla multiplication symbol × “rp = right-pointing arrow →

“lp = L “mp = element of; ∈

Samples

• vanilla delta δ
• italicized delta δ
• regular Capital Sigma Σ
• italicized Capital Sigma Σ
• bold Capital Sigma Σ

macros

@e = turn exactly one character bold