Finite State Automata

Gregory M. Kapfhammer

October 27, 2025

Learning objectives

Learning Objectives for Theoretical Machines

CS-204-1: Use both intuitive analysis and theoretical proof techniques to correctly distinguish between problems that are tractable, intractable, and uncomputable.
CS-204-2: Correctly use one or more variants of the Turing machine (TM) abstraction to both describe and analyze the solution to a computational problem.
CS-204-3: Correctly use one or more variants of the finite state machine (FSM) abstraction to describe and analyze the solution to a computational problem.
CS-204-4: Use a formal proof technique to correctly classify a problem according to whether or not it is in the P, NP, NP-Hard, and/or NP-Complete complexity class(es).
CS-204-5: Apply insights from theoretical proofs concerning the limits of either program feasibility or complexity to the implementation of both correct and efficient real-world Python programs.

Finite state automata are simplified Turing machines! Interesting!

Finite automata help with learning objective CS-204-3, in which you learn about finite state machines (FSMs) and their computational power. Let’s explore how constraints affect computability! Why is it beneficial to make these constraints? How does the FSM connect to practical computing?

What are finite automata?

Finite automata: Special, restricted case of Turing machines
Key restrictions: Head only moves right, never edits tape
Termination: Blank symbol ends input processing
Question: What problems can finite automata solve?
Question: How do they aid agents and regular expressions?

Finite automata model computation with severely limited resources! No memory beyond a fixed number of states and no ability to revisit previous input. Despite these constraints, they remain useful for pattern matching, lexical analysis, and network protocol verification. Although restricted, there are deterministic and nondeterministic versions. Let’s explore in detail!

Deterministic finite automata

Components of a deterministic finite automaton (DFA):
- Alphabet of symbols (including blank)
- Finite set of states (start, accept, reject)
- Transition function: \((q, x) \rightarrow q'\)
Computation: read symbol, transition to new state, move right
Always halts: after at most \(n\) steps for input length \(n\)
Deterministic: exactly one possible transition from each state

DFAs are the simplest computational model! They can recognize patterns in strings but cannot count unbounded values or maintain memory.

Understanding simple DFAs

Nodes represents states, arrows are transitions on input symbols
Acceptance state(s) indicated by double circles on nodes
Implicit transitions: unspecified transitions go to qreject
DFA is visually similar to the Turing machine’s state diagram
Behavior of two simple DFAs:
- containsGAGA: accepts strings with substring “GAGA”
- multipleOf5: accepts decimal numbers divisible by 5
What do they look like? How do they work? Key benefits?

DFA examples: `containsGAGA`

DFA for containsGAGA

DFA examples: `multipleOf5`

DFA for multipleOf5

Implementing a simple DFA simulator

def simulate_dfa(transitions: dict, start: str, accept: set,
                 input_string: str) -> bool:
    """Simulate a DFA on an input string."""
    current_state = start
    for symbol in input_string:
        if (current_state, symbol) in transitions:
            current_state = transitions[(current_state, symbol)]
        else:
            return False
    return current_state in accept

# DFA for strings ending in 'AB'
transitions = {
    ('q0', 'A'): 'q1', ('q0', 'B'): 'q0',
    ('q1', 'A'): 'q1', ('q1', 'B'): 'q2',
    ('q2', 'A'): 'q1', ('q2', 'B'): 'q0'
}
accept = {'q2'}

print(f"'AAAB' accepted: {simulate_dfa(transitions, 'q0', accept, 'AAAB')}")
print(f"'ABAB' accepted: {simulate_dfa(transitions, 'q0', accept, 'ABAB')}")
print(f"'ABBA' accepted: {simulate_dfa(transitions, 'q0', accept, 'ABBA')}")

'AAAB' accepted: True
'ABAB' accepted: True
'ABBA' accepted: False

Define nondeterministic finite automata (NFA)

Nondeterminism: multiple possible transitions from same state
Epsilon transitions: can transition without reading input
Acceptance: accept if any computational path accepts
Key insight: NFAs can be “simpler” than equivalent DFAs

You can think of NFAs as exploring multiple possibilities simultaneously! An NFA is like a DFA that can “clone itself” at decision points. If any clone reaches an accept state, the entire computation accepts the input! Wait, sound familiar to the nondeterministic Turing machine? Oh, don’t forget that they are more expressive, not more powerful!

NFA visualization: cloning and choices

Viewing an NFA in light of a TM or a DFA

What are connections between an NFA and DFA or TM?

Grasping automaton acceptance

Accept: if any clone reaches accept state
Reject: if all clones reject
Undefined: if all clones enter infinite \(\epsilon\)-loop
Essentially, same conception as nondeterministic Turing machines!
Next Step: Explore a DFA or an NFA that accepts the strings “AA”, “AGA”, and an “A” followed by any combination of C’s and G’s (provided there is at least one C or G). How would we build this finite automaton?
There are different, equivalent ways to build this finite automaton!
- Use a blank symbol
- Use the \(\epsilon\)-transition
- Combine both blank symbols and \(\epsilon\)-transitions

Using a blank symbol

An NFA that leverages a blank symbol

Using the \(\epsilon\)-transition

An NFA that uses the \(\epsilon\)-transition

Accepting multiples of 2 or 3 letters

NFA for input strings with length that is a multiple of 2 or 3

Understanding the prior NFA

Problem: accept strings of \(n\) G’s where \(n\) is divisible by 2 or 3
NFA advantage: decomposes into two independent checks
Top path: checks divisibility of string length \(n\) by 2
Bottom path: checks divisibility of string length \(n\) by 3
Equivalent DFA: would be more complex and perhaps less intuitive
NFAs often model problems more “naturally”!
- Make sure that you see how it uses the blank symbol
- Confirm that you understand how it uses the \(\epsilon\)-transition
- Could you build this NFA as a DFA? Go ahead, try it out!

Converting NFAs to DFAs

Key theorem: Every NFA has an equivalent DFA
Subset construction: DFA states represent sets of NFA states
State explosion: DFA may have up to \(2^k\) states for \(k\) NFA states
Implication: Nondeterminism doesn’t increase computational power for finite automata! Instead, it enables us to design “simpler” or more “expressive” machines. Get the trade-off?

Nondeterminism provides convenience, not power: any language recognized by an NFA can also be recognized by a DFA. The DFA may be exponentially larger, but it can be built and it solves the same problem!

NFA to DFA conversion algorithm

Create DFA start state: set containing NFA start state plus all states reachable via \(\epsilon\)-transitions
For each DFA state and symbol: compute the set of NFA states reachable
Mark DFA states as accepting: if they contain any NFA accepting state
Repeat until no new DFA states discovered
Result: DFA with states as subsets of NFA states

Subset construction systematically tracks all possible NFA states. Each DFA state represents “all places the NFA could be” after reading the input so far. This construction proves NFAs and DFAs are equally powerful!
Key questions: what would the DFA that arises from this conversion process look like for a prior NFA? Which one do you prefer? Why?

Final DFA arising from an NFA

Completed DFA resulting from an original NFA

Grasping trade-offs of the DFA

What do NFAs and DFAs have in common?
- Both are finite automata consisting of:
  - States
  - Transitions
- Both recognize regular languages
- Both support the blank symbol
- Both have a start state and an accepting state
Observation: DFA often has more states than original NFA
Trade-off: clarity versus size in automaton design
When would you prefer an NFA over a DFA? Why?

Regular expressions

Regular expressions: concise pattern description language
Equivalent to finite automata: same power as DFAs or NFAs
Practical applications: text search, validation, lexical analysis
Theoretical importance: define regular languages precisely

Regular expressions bridge theory and practice as they’re both a formal mathematical notation for describing languages and a practical tool used daily by programmers for pattern matching and text processing!

Find an open-source Python project that contains a regular expression!

What did you find? How does it work?
What are the benefits and limitations?
Share the link and a code segment
Here is an example from GatorGrader:

MULTILINECOMMENT_RE_JAVA = r"""/\*([^*]|[\r\n]|(\*+([^*/]|[\r\n])))*\*+/"""
SINGLELINECOMMENT_RE_JAVA = r"""^(?:[^"/\\]|\"(?:[^\"\\]|\\.)*
\"|/(?:[^/"\\]|\\.)|/\"(?:[^\"\\]|\\.)*\"|\\.)*//(.*)$"""
SINGLELINECOMMENT_RE_PYTHON = r"""^(?:[^"#\\]|\"(?:[^\"\\]|\\.)*\"|
/(?:[^#"\\]|\\.)|/\"(?:[^\"\\]|\\.)*\"|\\.)*#(.*)$"""
MULTILINECOMMENT_RE_PYTHON = r'^[ \t]*"""(.*?)"""[ \t]*$'

Define “pure” regular expressions

The basics of pure regular expression

Define a good starting point for grasping regular expressions
Help us to think about how they relate to DFAs and NFAs
Although not exactly how they often appear in programming languages, many of the concepts are very similar!

Regular expression operations

Operations available in regular expressions

Build up more useful pure regular expressions with operations. Using concatenation, alteration, or Kleene star always results in a new regular expression!

Key details about regular expression

Empty string \(\epsilon\): matches nothing (zero characters)
Single character \(a\): matches exactly that character
Concatenation (written as \(r_1 r_2\)): match \(r_1\) then \(r_2\)
Alternation (written as \(r_1 | r_2\)): match \(r_1\) or \(r_2\)
Kleene star (written as \(r^*\)): match \(r\) zero or more times
All regular languages can be created from these operations
A language is regular if some regular expression describes it
Or, a regular expression describes a regular language
Let’s look at some examples so we better grasp how they work!

Regular expression examples

Examples of pure regular expressions and the language that they describe

Pure regular expression notation

Pattern matching: describe sets of strings concisely
Practical extensions:
- . means any char
- + means one or more
- [...] is a character class
- [a-z] matches any character in range
- [^abc] matches any character except those listed
- These are all “syntactic sugar” for convenience
Can you write a regex for email addresses?
How do you test a regular expressions’ correctness?

Regular expressions in Python

import re

def test_pattern(pattern: str, test_strings: list) -> None:
    """Test a regex pattern against multiple strings."""
    regex = re.compile(pattern)
    for s in test_strings:
        match = regex.fullmatch(s)
        print(f"'{s}': {'Match' if match else 'No match'}")

# pattern: strings starting with 'A' and ending with 'B'
pattern = r'A.*B'
test_strings = ['AB', 'ACCCB', 'AXYZB', 'ABC', 'BA']
print("Pattern: A.*B (start with A, end with B)")
test_pattern(pattern, test_strings)

# pattern: exactly 3 digits
print("\nPattern: [0-9]{3} (exactly 3 digits)")
pattern2 = r'[0-9]{3}'
test_strings2 = ['123', '456', '12', '1234', 'abc']
test_pattern(pattern2, test_strings2)

Pattern: A.*B (start with A, end with B)
'AB': Match
'ACCCB': Match
'AXYZB': Match
'ABC': No match
'BA': No match

Pattern: [0-9]{3} (exactly 3 digits)
'123': Match
'456': Match
'12': No match
'1234': No match
'abc': No match

Pattern matching for email

import re

# pattern for simple email validation
pattern = r'[a-zA-Z0-9]+@[a-zA-Z0-9]+\.[a-zA-Z]+'
test_strings = [
    'user@example.com',
    'test.user@domain.org',
    'invalid@',
    '@invalid.com',
    'no-at-sign.com'
]
print("Email pattern: [a-zA-Z0-9]+@[a-zA-Z0-9]+\\.[a-zA-Z]+")
test_pattern(pattern, test_strings)

Email pattern: [a-zA-Z0-9]+@[a-zA-Z0-9]+\.[a-zA-Z]+
'user@example.com': Match
'test.user@domain.org': No match
'invalid@': No match
'@invalid.com': No match
'no-at-sign.com': No match

Regex and finite automata

Two-way conversion: regex ↔︎ NFA ↔︎ DFA
Regex to NFA: build NFA compositionally from operations
DFA to regex: simplify DFA by labeling transitions with regex
Same power: all models recognize same regular languages!

Conversion between models is possible:
- Convert a regular expression to a DFA or an NFA
- Convert a DFA or an NFA to a regular expression
Multiple formalisms give different viewpoint: DFAs are easiest to simulate, NFAs are easiest to design, and regexes are easiest to program.

Regular languages

Regular language: decided by some DFA (or NFA, or regex)
Three equivalent definitions:
- DFA-decidable
- NFA-decidable
- Regex-describable
Key question: Are all decidable languages regular?
Answer: No, some decidable languages are not regular!
Key computational hierarchy: regular languages are a proper subset of decidable languages. Computational models differ in power, and resource limitations, like finite memory, restrict what can be computed!

Regular languages are decidable

Claim: If a language is regular, then it’s decidable
Proof: Every DFA is a special case of Turing machine
Therefore: Any language decided by DFA is decided by TM
Implication: Regular ⊆ Decidable

Trivial but important: the containment Regular ⊆ Decidable is obvious from definitions. Specifically, we know that a finite automaton is a restricted Turing machine. Next, we want to explore whether there are decidable languages that are not regular by exploring the language defined by \(G^nT^n\). In a moment we will also implement this language in Python, further confirming that it is decidable. Okay, let’s dive in!

\(G^nT^n\) is decidable but not regular

Language: \(\{G^nT^n : n \geq 0\} = \{\epsilon, GT, GGTT, GGGTTTT, ...\}\)
Decidable: Turing machine (or Python program) can count G’s and T’s
Not regular: DFA has finite states and cannot count unbounded values
Proof technique: suppose DFA exists, derive a logical contradiction
Contradiction: DFA must accept strings it shouldn’t
Conclusion: \(G^nT^n\) is not a regular language for any \(n \geq 0\)

\(G^nT^n\) requires unbounded counting: a DFA would need different states for each possible value of \(n\), but DFAs have only finitely many states. This proves some decidable languages are not regular, a key result for this class!

Explore \(G^nT^n\) in Python

Key result: \(G^nT^n\) is not regular

Pigeonhole principle applied to DFA

Pigeonhole principle: more G’s than states forces a cycle
Cycle traversal: can repeat or skip, creating wrong string
“Pumping” the cycle: generates strings not in language
This technique generalizes to the pumping lemma!

Compare Turing machines and DFAs

The finite memory of a DFA that makes it more limited than a Turing machine. But Turing machines also have a finite number of states. Why don’t they have the same problem?
They use a tape to recall as much information as needed!
They can record infinitely many distinct strings on its tape.
So although it has a finite set of states, it has infinitely many possible configurations. Do you now see the power of unbounded memory in a Turing machine?
Okay, now we are ready to explore the pumping lemma!

Pumping lemma

Pumping: repeating a substring zero or more times
Example: “TGACGT” → pump “AC” → “TGACACGT” or “TGT”
Still in language: pumped string remains valid
Insight: regular languages always allow pumping long strings

Pumping exploits finite-state limitation: if a DFA accepts a long string, it must revisit states, creating a cycle that can be repeated or skipped. This forced repetition is the essence of pumping, helps in proof by contradiction.

Pumping example in language

Pumping substrings in ATC|TG(AC)GT

Original string: underlined portion can be repeated
Pumped versions: repeat 0, 1, 2, or more times
All accepted: because pumped portion corresponds to DFA cycle
Critically, all regular languages have this property!

Formal definition of pumping

Define the concept of pumping a language \(L\)

Pumping for regular languages

Pumping lemma statement

Theorem: If language is regular and infinite, it can be pumped
Constant \(k\): depends on the DFA (usually number of states)
Every long string: length ≥ \(k\) can be decomposed and pumped
Contrapositive: if no pumping possible, language is not regular
Main use: prove languages are not regular!
Key: Instead of using fact that “regular languages can be pumped,” we use the equivalent statement “if it can’t be pumped, then it’s not regular.”

Proving non-regularity of language

Proof by contradiction: the pumping lemma is a powerful tool. To prove \(L\) is not regular, assume that it is and show that no matter how we pump, we eventually generate a string not in \(L\). This contradicts regularity and proves \(L\) is not regular.
Mechanical flow of the proof:
- Assume \(L\) is a regular language
- Apply pumping lemma to \(L\) and accept its conditions
- Produce a fixed, but unknown, and sufficiently large cutoff \(N\)
- Creatively pick a string \(S\) that is in \(L\) and has length ≥ \(N\)
- Consider all valid substrings \(R\) of \(S\) that are “pumpable”
- Show that pumping \(R\) produces a string not in \(L\)
- Note that there is a contradiction of initial assumption
- Conclude that \(L\) is not a regular language!

Combining regular languages

Closure properties of regular languages

Union: \(L_1 \cup L_2\) is regular if \(L_1\), \(L_2\) regular
Concatenation: \(L_1 L_2\) is regular if \(L_1\), \(L_2\) regular
Complement: \(\overline{L}\) is regular if \(L\) regular
Intersection: \(L_1 \cap L_2\) is regular if \(L_1\), \(L_2\) regular
Closure properties: regular languages closed under operations
Proof exercise: try to construct DFAs for operations!

Applications of closure properties

Proving non-regularity: if \(L\) regular and \(\overline{L}\) is not, contradiction!
SameGT example: equal numbers of G’s and T’s is not regular
Proof: combine \(G^nT^n\) result with closure properties
Java programs: language of syntactically valid Java is not regular
Practical implication: need more powerful parsers than DFAs

Closure properties are proof tools: they let us build new non-regularity results from known ones. Programming language syntax generally requires context-free grammars (more powerful than regular expressions) for parsing!

Finite automata and regular languages: limited but useful!

DFAs: simplest computational model, deterministic state transitions
NFAs: allow nondeterminism and \(\epsilon\)-transitions, equal power to DFAs
Regular expressions: concise notation, equivalent to DFAs/NFAs
Regular languages: decided by DFAs, described by regex
Pumping lemma: tool for proving languages are not regular
Closure properties: regular languages closed under many operations

Finite automata reveal computational limits: despite their simplicity and practical utility, they cannot recognize all decidable languages.