The Central Idea
A finite automaton is a finite-state machine used as a recognizer.
It receives a string of input symbols, processes those symbols one at a time, and finishes in some state.
If the final state is designated as accepting, the string is accepted.
Otherwise, the string is rejected.
Automata as Recognizers
The central question is not merely
What state does the machine reach?
but
Does the input string satisfy the pattern the machine was designed to recognize?
Automata therefore connect state transitions with formal language recognition.
Alphabet
An alphabet is a finite set of symbols.
It is commonly written
\[ \Sigma. \]For binary strings,
\[ \Sigma=\{0,1\}. \]For a simple letter system, we might use
\[ \Sigma=\{a,b\}. \]Strings
A string over an alphabet is a finite sequence of symbols chosen from that alphabet.
If
\[ \Sigma=\{0,1\}, \]then examples of strings include
\[ 0,\qquad 1,\qquad 01,\qquad 1011,\qquad 00010. \]The Empty String
The unique string containing no symbols is the empty string.
It is commonly written
\[ \varepsilon. \]Its length is
\[ |\varepsilon|=0. \]All Strings over an Alphabet
The set of all finite strings over \(\Sigma\) is written
\[ \Sigma^*. \]For
\[ \Sigma=\{0,1\}, \]the set \(\Sigma^*\) includes
\[ \varepsilon,\ 0,\ 1,\ 00,\ 01,\ 10,\ 11,\ 000,\ldots \]Language
A language over \(\Sigma\) is any set of strings drawn from \(\Sigma^*\).
Formally,
\[ \boxed{L\subseteq\Sigma^*}. \]An automaton recognizes a language by accepting exactly the strings in that language.
Example Language
Let
\[ \Sigma=\{0,1\}. \]Consider the language
\[ L=\{w\in\Sigma^*:w\text{ ends in }1\}. \]Examples in \(L\) include
\[ 1,\qquad 01,\qquad 101,\qquad 1111. \]Examples not in \(L\) include
\[ \varepsilon,\qquad 0,\qquad 10,\qquad 1010. \]Deterministic Finite Automaton
A deterministic finite automaton, abbreviated DFA, consists of five components:
\[ \boxed{(Q,\Sigma,\delta,q_0,F)}. \]Here:
- \(Q\) is a finite set of states;
- \(\Sigma\) is the input alphabet;
- \(\delta\) is the transition function;
- \(q_0\in Q\) is the initial state;
- \(F\subseteq Q\) is the set of accepting states.
The DFA Transition Function
For a DFA,
\[ \delta:Q\times\Sigma\to Q. \]Every current-state/input pair determines exactly one next state.
That uniqueness is what makes the machine deterministic.
Accepting States
Accepting states are distinguished from ordinary states.
If the machine finishes in a state
\[ q\in F, \]then the processed string is accepted.
If the final state is outside \(F\), the string is rejected.
Acceptance Depends on the Final State
A string may pass through an accepting state during processing and still be rejected if later symbols move the machine elsewhere.
The decision is made only after the entire input string has been processed.
Example DFA: Strings Ending in 1
Use two states:
\[ q_0=\text{last symbol is not }1 \]and
\[ q_1=\text{last symbol is }1. \]Let \(q_0\) be the initial state and let
\[ F=\{q_1\}. \]Transition Table for Strings Ending in 1
| Current State | Input 0 | Input 1 |
|---|---|---|
| \(q_0\) | \(q_0\) | \(q_1\) |
| \(q_1\) | \(q_0\) | \(q_1\) |
Process an Accepted String
Process
\[ 101. \]Starting in \(q_0\):
\[ q_0\xrightarrow{1}q_1 \xrightarrow{0}q_0 \xrightarrow{1}q_1. \]Since \(q_1\) is accepting,
\[ \boxed{101\text{ is accepted}}. \]Process a Rejected String
Process
\[ 110. \]Starting in \(q_0\):
\[ q_0\xrightarrow{1}q_1 \xrightarrow{1}q_1 \xrightarrow{0}q_0. \]Since \(q_0\notin F\),
\[ \boxed{110\text{ is rejected}}. \]Extended Transition Function
The ordinary transition function processes one input symbol.
An extended transition function processes an entire string.
It is often written
\[ \delta^*:Q\times\Sigma^*\to Q. \]Thus,
\[ \delta^*(q_0,w) \]means the state reached after processing the complete string \(w\) from \(q_0\).
Recursive Definition of \(\delta^*\)
The empty string changes no state:
\[ \delta^*(q,\varepsilon)=q. \]If \(w\) is a string and \(a\) is one additional symbol, then
\[ \boxed{ \delta^*(q,wa) = \delta(\delta^*(q,w),a) }. \]This expresses string processing recursively.
The Language Recognized by a DFA
A DFA \(M\) recognizes the language
\[ L(M) = \{w\in\Sigma^*:\delta^*(q_0,w)\in F\}. \]In words, \(L(M)\) contains exactly the strings that take the machine from its start state to an accepting state.
Example: Even Number of 1s
Consider the language of binary strings containing an even number of \(1\)s.
Use states
\[ E=\text{even number of 1s seen} \]and
\[ O=\text{odd number of 1s seen}. \]Make \(E\) both the initial and accepting state.
Parity Automaton
| Current State | Input 0 | Input 1 |
|---|---|---|
| \(E\) | \(E\) | \(O\) |
| \(O\) | \(O\) | \(E\) |
Input \(0\) preserves parity.
Input \(1\) switches parity.
Why the Empty String Can Be Accepted
The empty string contains zero \(1\)s.
Zero is even.
Since the parity automaton begins in accepting state \(E\) and processes no symbols,
\[ \boxed{\varepsilon\text{ is accepted}}. \]Example: Strings Containing 01
To recognize binary strings containing the substring \(01\), use states that record progress toward detecting that pattern.
One useful design is:
- \(q_0\): no useful partial match;
- \(q_1\): the most recent relevant symbol is \(0\);
- \(q_2\): substring \(01\) has been seen.
Make \(q_2\) accepting.
Once the Pattern Is Found
If the language is
\[ \{w:w\text{ contains }01\}, \]then after \(01\) has occurred, later symbols cannot undo that fact.
Therefore, the accepting state can loop on both \(0\) and \(1\).
Trap States
A trap state, sometimes called a dead state or sink state, is a state from which the machine can never reach an accepting state.
Trap states are useful when an input permanently violates the pattern being recognized.
Example: Binary Strings with No 11
To recognize strings that never contain \(11\), use:
- \(q_0\): previous symbol is not \(1\);
- \(q_1\): previous symbol is \(1\);
- \(q_T\): forbidden substring \(11\) has occurred.
Once the machine reaches \(q_T\), it remains trapped there.
Nondeterministic Finite Automaton
A nondeterministic finite automaton, abbreviated NFA, allows a state/input pair to have:
- no possible next state;
- one possible next state;
- several possible next states.
The machine can therefore branch into several possible computational paths.
NFA Transition Function
For an NFA without \(\varepsilon\)-transitions, the transition function can be written
\[ \delta:Q\times\Sigma\to\mathcal{P}(Q), \]where \(\mathcal{P}(Q)\) is the power set of \(Q\).
The output is a set of possible next states.
Nondeterminism Is Not Randomness
An NFA is not modeled as choosing one transition randomly.
Conceptually, all permitted computational paths are considered.
The input is accepted if at least one valid path finishes in an accepting state.
NFA Acceptance
A string is accepted by an NFA if there exists at least one path from the initial state to an accepting state whose labels spell the entire input string.
One successful path is enough.
Why Nondeterminism Can Be Convenient
Nondeterminism often allows a compact machine to express a pattern without explicitly tracking every possibility in separate deterministic states.
This can make automata easier to design and reason about.
Epsilon Transitions
Some NFA definitions allow \(\varepsilon\)-transitions.
An \(\varepsilon\)-transition changes state without consuming an input symbol.
It is labeled
\[ \varepsilon. \]Epsilon Closure
The \(\varepsilon\)-closure of a state is the set of states reachable using zero or more \(\varepsilon\)-transitions.
The starting state itself is always included because zero such transitions are allowed.
DFA and NFA Expressive Power
Every DFA is automatically a special case of an NFA.
More surprisingly, every NFA has an equivalent DFA that recognizes exactly the same language.
Thus DFAs and NFAs have the same language-recognition power.
Subset Construction
An NFA can be converted to an equivalent DFA using the subset construction.
Each DFA state represents a set of NFA states that could simultaneously be active after reading the same input prefix.
Why the Power Set Appears
If an NFA has \(n\) states, then its equivalent DFA may need to represent subsets of those states.
There are
\[ 2^n \]possible subsets.
Therefore, the deterministic machine can in principle have exponentially more states.
Accepting States in Subset Construction
A DFA subset-state is accepting if it contains at least one accepting NFA state.
This matches the NFA rule that one successful branch is enough for acceptance.
Regular Languages
A language recognized by some finite automaton is called a regular language.
Thus,
\[ \boxed{ L\text{ is regular} \iff \text{some finite automaton recognizes }L }. \]Examples of Regular Patterns
Finite automata can recognize many finite-memory patterns, including:
- strings ending in a particular symbol;
- strings containing a fixed substring;
- strings avoiding a fixed substring;
- strings with even or odd parity;
- strings whose length has a fixed remainder modulo \(m\);
- strings matching many common search patterns.
Example: Length Divisible by 3
To recognize strings whose length is divisible by \(3\), use states
\[ q_0,\qquad q_1,\qquad q_2 \]representing the current length modulo \(3\).
Every input symbol advances the remainder:
\[ q_0\to q_1\to q_2\to q_0. \]Make \(q_0\) accepting.
Automata and Modular Counting
Finite automata can track quantities modulo a fixed integer because only finitely many remainders exist.
For modulus \(m\), the machine can use states
\[ 0,1,\ldots,m-1. \]This is a natural connection between finite-state computation and modular arithmetic.
Example: Binary Value Modulo 2
A binary string represents an even integer exactly when its last bit is \(0\).
Therefore, a two-state automaton remembering only the last bit is enough to recognize even binary numbers.
State Equivalence
Two DFA states are equivalent if no possible future input string can distinguish them with respect to acceptance.
If every suffix leads both states either to acceptance or both to rejection, the states carry the same future behavior.
Distinguishable States
Two states are distinguishable if there exists some input string that leads one state to acceptance and the other to rejection.
Such an input serves as evidence that the states cannot be merged.
DFA Minimization
DFA minimization seeks an equivalent deterministic automaton with the fewest states.
The process typically involves:
- removing unreachable states;
- identifying equivalent states;
- merging equivalent states.
Equivalent Automata
Two automata are equivalent when they recognize the same language.
They may have different:
- state names;
- numbers of states;
- diagram shapes;
- deterministic or nondeterministic structure.
What matters is the set of accepted strings.
Complementing a Complete DFA
For a complete DFA, the complement language can be recognized by swapping accepting and nonaccepting states.
If
\[ F \]is the original accepting set, use
\[ Q\setminus F \]as the new accepting set.
Why Completeness Matters
Swapping accepting and nonaccepting states works cleanly when every state/input pair has a defined transition.
Otherwise, missing transitions must first be handled, typically by adding a trap state.
Product Automata
Two DFAs can be combined into a product automaton.
Product states have the form
\[ (q_A,q_B), \]recording the current state of both machines simultaneously.
Intersection of Regular Languages
A product automaton can recognize
\[ L_A\cap L_B \]by accepting exactly when both component machines are in accepting states.
This shows that regular languages are closed under intersection.
Union of Regular Languages
The same product construction can recognize
\[ L_A\cup L_B \]by accepting when at least one component state is accepting.
Therefore, regular languages are also closed under union.
Finite Automata Have Limited Memory
A finite automaton has only finitely many states.
Therefore, it can remember only finitely many distinguishable situations.
It cannot count an arbitrarily large quantity exactly unless only a finite property of that quantity matters, such as its parity or remainder modulo a fixed integer.
Why Some Patterns Need More Power
A finite automaton cannot store an unbounded stack of symbols or an arbitrarily large exact counter.
More powerful computational models are required for languages whose recognition demands unbounded memory.
This distinction becomes important later in formal-language theory.
Automata in Text Processing
Finite automata are natural models for:
- pattern matching;
- token recognition;
- lexical analysis;
- input validation;
- search systems.
Automata in Control Systems
Automata also model finite collections of operating modes and allowable transitions.
Examples include:
- protocol controllers;
- user-interface states;
- device modes;
- workflow steps;
- simple robotics controllers.
Automata in Verification
A system specification can sometimes be represented as an automaton.
Another automaton can represent allowed or forbidden event sequences.
Comparing these structures provides a finite framework for certain verification problems.
Common Error: Confusing States with Input Symbols
States belong to
\[ Q. \]Input symbols belong to
\[ \Sigma. \]They play different roles and should not be interchanged.
Common Error: Accepting Too Early
Reaching an accepting state before the input ends does not guarantee acceptance.
The machine must process the entire string first.
Common Error: Rejecting an NFA Because One Path Fails
An NFA accepts if at least one computational path succeeds.
A failed branch does not force rejection when another branch reaches an accepting state.
Common Error: Treating Nondeterminism as Random Choice
Nondeterminism is a mathematical branching model, not a probability model.
No probabilities are assigned to the alternative transitions.
Common Error: Forgetting the Empty String
The empty string
\[ \varepsilon \]must be considered whenever a language or automaton may accept without consuming any symbols.
Common Error: Leaving a DFA Transition Undefined
In a complete DFA, every pair
\[ (q,a)\in Q\times\Sigma \]must have exactly one next state.
A trap state can be added when a transition has no other useful destination.
Common Error: Assuming Different Diagrams Mean Different Languages
Two automata may look very different and still recognize the same language.
Language equivalence is determined by accepted strings, not diagram shape.
A Reliable Procedure for Processing a DFA Input
- Start at \(q_0\).
- Read the first input symbol.
- Use the transition function to move to the next state.
- Continue one symbol at a time.
- After the final symbol, inspect the current state.
- Accept if the state lies in \(F\); otherwise reject.
A Reliable Procedure for Designing a DFA
- State the language condition precisely.
- Identify what information about the input prefix must be remembered.
- Create one state for each behaviorally distinct memory condition.
- Choose the initial state.
- Define a transition for every state/input pair.
- Mark the states corresponding to successful completion as accepting.
- Test strings that should be accepted and rejected.
A Reliable Procedure for Converting an NFA to a DFA
- Begin with the NFA start state or its \(\varepsilon\)-closure.
- Treat that set of NFA states as one DFA state.
- For each input symbol, compute every NFA state reachable from the current set.
- Take any required \(\varepsilon\)-closures.
- Create a DFA state for each new subset encountered.
- Repeat until no new subsets appear.
- Mark a subset accepting if it contains an accepting NFA state.
Example: Full DFA Processing Workflow
Use the parity DFA:
| State | 0 | 1 |
|---|---|---|
| \(E\) | \(E\) | \(O\) |
| \(O\) | \(O\) | \(E\) |
Let \(E\) be initial and accepting.
Process
\[ 10110. \]The run is
\[ E \xrightarrow{1} O \xrightarrow{0} O \xrightarrow{1} E \xrightarrow{1} O \xrightarrow{0} O. \]Since \(O\) is not accepting,
\[ \boxed{10110\text{ is rejected}}. \]Practice 1: Alphabet
If
\[ \Sigma=\{a,b\}, \]is \(abba\) a string over \(\Sigma\)?
Practice 2: Empty String
What is the length of
\[ \varepsilon? \]Practice 3: DFA Components
What does the set \(F\) represent in
\[ (Q,\Sigma,\delta,q_0,F)? \]Practice 4: DFA Transition
If
\[ \delta(q_1,0)=q_2, \]where does the machine move from \(q_1\) on input \(0\)?
Practice 5: Acceptance
A DFA finishes processing a string in state \(q_3\), and
\[ q_3\in F. \]Is the string accepted or rejected?
Practice 6: Nondeterminism
An NFA has two possible transitions on the same input symbol. Does this violate the definition of an NFA?
Practice 7: NFA Acceptance
Three NFA paths process the entire input. Two reject and one reaches an accepting state.
Is the string accepted?
Practice 8: Regular Language
What do we call a language recognized by some finite automaton?
Practice 9: Complement
How can the complement language of a complete DFA be obtained?
Practice 10: State Memory
Why can a finite automaton track parity indefinitely even though it has only finitely many states?
Practice Answers
Practice 1
Yes. Every symbol in \(abba\) belongs to
\[ \Sigma=\{a,b\}. \]Practice 2
\[ \boxed{|\varepsilon|=0}. \]Practice 3
\(F\) is the set of
\[ \boxed{\text{accepting states}}. \]Practice 4
The machine moves to
\[ \boxed{q_2}. \]Practice 5
Since the final state lies in \(F\),
\[ \boxed{\text{the string is accepted}}. \]Practice 6
No.
Multiple possible next states are allowed in an NFA.
Practice 7
Yes.
An NFA accepts if at least one valid path finishes in an accepting state.
Practice 8
\[ \boxed{\text{regular language}}. \]Practice 9
For a complete DFA, swap accepting and nonaccepting states:
\[ F\longrightarrow Q\setminus F. \]Practice 10
Parity requires remembering only two possibilities:
\[ \text{even} \]or
\[ \text{odd}. \]The exact number of \(1\)s is unnecessary.
What to Remember
- An automaton processes strings over a finite alphabet.
- A DFA is described by \((Q,\Sigma,\delta,q_0,F)\).
- A string is accepted when the complete input leaves the machine in an accepting state.
- The extended transition function processes whole strings.
- An NFA may have several possible next states for one state/input pair.
- An NFA accepts if at least one complete path reaches an accepting state.
- \(\varepsilon\)-transitions consume no input symbol.
- Every NFA has an equivalent DFA.
- Languages recognized by finite automata are called regular languages.
- Finite automata can remember only finitely many distinguishable conditions.
The central habit is to identify exactly what information about the input prefix must be remembered so that acceptance can be determined after the full string is processed.
Where We Go Next
Automata recognize collections of strings, but to discuss those collections precisely we need a formal language for alphabets, strings, concatenation, repetition, grammars, and language operations.
The next lesson, Introductory Formal Languages, develops that vocabulary and connects symbolic languages to automata and computation.