Finite State Machines for Parsing and Validation

Finite state machines are an extension topic beyond most interviews; they pay off on parsing and validation questions (valid number, UTF-8 validation, string to integer), on pattern matching, and whenever a messy chain of if statements can be replaced by a small, checkable table.

Intuition

A deterministic finite automaton (DFA) reads its input one symbol at a time. It has:

• a finite set of states, one of which is the start state;
• a transition function: from a state, on a symbol, go to exactly one next state;
• a set of accepting states.

After reading the whole input, the input is accepted if the machine stands in an accepting state. A missing transition means the input can no longer be valid; treat it as a jump to a "dead" state and reject immediately.

Why this helps in interviews: each state names exactly what you know about the prefix read so far ("seen a sign", "inside the fraction", "expecting continuation bytes"), so every rule of the format becomes one table entry instead of one more nested condition. The state can also be a number: to check divisibility of a binary number by k, the state is "the prefix value mod k", which gives a k-state DFA.

A nondeterministic automaton (NFA) may have several possible next states, or move without consuming input (an epsilon move). Simulating it means tracking the set of states you could be in. Regular expressions translate naturally into NFAs: a starred token x* is a state that can loop on x or be skipped. Every NFA has an equivalent DFA, but the conversion can blow up exponentially; simulating the set of states directly costs O(states) per input symbol.

Limits: finite automata cannot count without bound, so balanced parentheses or nested structures need a stack or a counter, not a pure DFA.

When to use it in interviews / OAs

• Validation of a textual format: numbers with signs, decimals and exponents; identifiers; dates; IP addresses; byte encodings such as UTF-8.
• Parsing with a few modes: string to integer (skip spaces, read sign, read digits, stop), tokenizers, CSV fields with quotes.
• Pattern matching: regular expressions with . and * (as an alternative to DP), and many "is t a subsequence of s" queries against one s.
• Running remainders: binary prefix divisible by k, streaming checks that only need a bounded summary.
• State-machine DP: buy/sell/cooldown stock problems are DP over automaton states (holding, sold, resting).

Template

A table-driven DFA: valid number

A valid number is an optional sign, then digits with an optional dot (at least one digit overall), then optionally e or E followed by an optionally signed integer.

DIGIT, SIGN, DOT, EXP = "digit", "sign", "dot", "exp"


def char_class(ch: str) -> str | None:
    if ch.isascii() and ch.isdigit():
        return DIGIT
    if ch in "+-":
        return SIGN
    if ch == ".":
        return DOT
    if ch in "eE":
        return EXP
    return None


# state -> {character class -> next state}; anything missing leads to a dead state
NUMBER_DFA = {
    "start": {SIGN: "sign", DIGIT: "int", DOT: "dot_no_int"},
    "sign": {DIGIT: "int", DOT: "dot_no_int"},
    "int": {DIGIT: "int", DOT: "dot_after_int", EXP: "exp"},
    "dot_after_int": {DIGIT: "frac", EXP: "exp"},
    "dot_no_int": {DIGIT: "frac"},
    "frac": {DIGIT: "frac", EXP: "exp"},
    "exp": {SIGN: "exp_sign", DIGIT: "exp_int"},
    "exp_sign": {DIGIT: "exp_int"},
    "exp_int": {DIGIT: "exp_int"},
}
ACCEPTING = {"int", "dot_after_int", "frac", "exp_int"}


def is_number(s: str) -> bool:
    state = "start"
    for ch in s:
        state = NUMBER_DFA[state].get(char_class(ch))
        if state is None:
            return False  # dead state: no valid continuation exists
    return state in ACCEPTING

"4." ends in dot_after_int, which accepts; "." ends in dot_no_int, which does not. Each such decision is visible in the table, which is the whole point.

A numeric state: divisibility of binary prefixes

def divisible_prefixes(bits: list[int], k: int) -> list[bool]:
    """For each prefix of a binary number (most significant bit first), is it divisible by k?"""
    state, out = 0, []  # state = prefix value mod k: a DFA with k states
    for b in bits:
        state = (state * 2 + b) % k
        out.append(state == 0)
    return out

A counter as the state: UTF-8 validation

A UTF-8 character is one byte 0xxxxxxx, or a leading byte 110xxxxx, 1110xxxx or 11110xxx followed by 1, 2 or 3 bytes of the form 10xxxxxx. The only state needed is how many continuation bytes are still expected:

def valid_utf8(data: list[int]) -> bool:
    expected = 0  # continuation bytes still owed by the current character
    for byte in data:
        if expected == 0:
            if byte >> 7 == 0:
                continue  # single-byte character
            if byte >> 5 == 0b110:
                expected = 1
            elif byte >> 4 == 0b1110:
                expected = 2
            elif byte >> 3 == 0b11110:
                expected = 3
            else:
                return False  # a stray continuation byte or an invalid leading byte
        else:
            if byte >> 6 != 0b10:
                return False
            expected -= 1
    return expected == 0  # the input must not stop in the middle of a character

NFA simulation: regular expressions with . and *

Compile the pattern into tokens; state i means "the first i tokens are matched". A starred token can repeat (stay in i) or be skipped for free (an epsilon move to i + 1):

def regex_match(s: str, p: str) -> bool:
    tokens: list[tuple[str, bool]] = []  # (character, starred)
    for ch in p:
        if ch == "*":
            tokens[-1] = (tokens[-1][0], True)
        else:
            tokens.append((ch, False))
    n = len(tokens)

    def closure(states: set[int]) -> set[int]:
        """Add every state reachable by skipping starred tokens."""
        stack, seen = list(states), set(states)
        while stack:
            i = stack.pop()
            if i < n and tokens[i][1] and i + 1 not in seen:
                seen.add(i + 1)
                stack.append(i + 1)
        return seen

    current = closure({0})
    for ch in s:
        moved = set()
        for i in current:
            if i < n and tokens[i][0] in (ch, "."):
                moved.add(i if tokens[i][1] else i + 1)  # a starred token may match again
        current = closure(moved)
        if not current:
            return False
    return n in current

The subsequence automaton: many queries against one string

State i means "the first i characters of s are used up". From state i on character c, jump to just after the next occurrence of c at or after i:

def subsequence_checker(s: str):
    n = len(s)
    nxt: list[dict[str, int]] = [{} for _ in range(n + 1)]  # nxt[i][c] = first j >= i with s[j] == c
    for i in range(n - 1, -1, -1):
        nxt[i] = {**nxt[i + 1], s[i]: i}

    def is_subsequence(t: str) -> bool:
        state = 0
        for ch in t:
            j = nxt[state].get(ch)
            if j is None:
                return False
            state = j + 1
        return True

    return is_subsequence

Complexity

• Running a DFA: O(length of the input), O(1) extra space beyond the table.
• divisible_prefixes and valid_utf8: O(n) time, O(1) extra space (besides the output).
• regex_match: O(|s| * |p|) time, O(|p|) space, the same bound as the DP solution.
• Subsequence automaton: O(n * alphabet) preprocessing and memory, then O(|t|) per query.

Common pitfalls

• Forgetting the dead state. Look up transitions with .get and reject on a miss, instead of raising an error or silently staying put.
• Wrong accepting set. Decide explicitly which partial inputs are complete: "1." and ".5" are numbers in most definitions, ".", "e5" and "1e" are not.
• Character classes. Python's str.isdigit also accepts non-ASCII digits such as "²"; check isascii() when the format is ASCII only.
• Not applying the epsilon closure at the start and after every step of an NFA, which misses matches such as "a*b*" on an empty string.
• Expecting a DFA to count. Balanced brackets, nesting depth or "equal numbers of a and b" need a stack or counters.
• Ending in the middle of a token: a UTF-8 sequence cut short or an exponent without digits must be rejected at the end of the input.

Interview variations

• Valid number: the DFA above (whitespace trimming, if allowed, happens before running it).
• String to integer (atoi): states for leading spaces, sign, digits and done, with clamping to the 32-bit range.
• UTF-8 validation: the counter machine above.
• Binary prefix divisible by 5: the remainder DFA.
• Regular expression matching (. and *): NFA simulation or DP; wildcard matching (? and *) works the same way with * matching any run of characters.
• Is subsequence with many queries and number of matching subsequences: the subsequence automaton, or buckets of words waiting for their next character.
• Best time to buy and sell stock with cooldown or fee: DP over the states holding, sold and resting.