Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 59 ยท Getting Started

Applications of Automata

See where automata are used in practice: lexical analysis, string search, protocol state machines, game logic and hardware, with runnable Python examples.

Automata can look like a classroom exercise, but a state machine is one of the most widely used designs in software and hardware. Any time a system has a limited number of situations ("modes") and reacts to a stream of inputs by moving between them, you are looking at an automaton, whether or not the author used the word.

This lesson tours the main applications and builds two of them. It previews the vocabulary that the next chapter defines carefully: states, transitions, a start state and accepting states.

Where automata appear

Software

Lexers Split source code into tokens
Text search Regex and pattern matching
Validation Emails, numbers, dates

Regular languages power all three.

1 / 3

Lexical analysis in compilers

The first phase of a compiler reads raw characters and groups them into tokens: identifiers, numbers, keywords, operators. Each token class is a regular language, and the lexer is a finite automaton that runs through the source text, remembering only which token it is currently inside. Tools such as lex and flex take token patterns (regular expressions), convert them to a single DFA and generate the scanning code.

Searching for a pattern in text with grep, an editor's find box or a database LIKE/REGEXP filter uses finite automata. Fast algorithms like Knuth-Morris-Pratt are really DFAs in disguise: one state per prefix of the pattern already matched. The advantage is guaranteed linear time: each text character is examined once.

Network protocols and UI flows

A TCP connection moves through states such as CLOSED, LISTEN, SYN_RECEIVED and ESTABLISHED, driven by packets and timeouts. Checkout flows (cart, address, payment, confirmation) and user-interface screens are state machines too. Writing them as explicit automata makes illegal sequences, like paying before choosing an address, impossible to express.

Hardware

Digital circuits with memory, from vending machines to CPU control units, are finite state machines built out of flip-flops. The Mealy and Moore machines you will meet later in this chapter are the hardware engineer's version of the automaton.

Example 1: a tokenizer as a state machine

The tokenizer below classifies a string into numbers (digits with an optional single decimal point) and identifiers (a letter followed by letters or digits). It moves between three working states, exactly like a DFA.

Python A tiny lexer driven by states

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The lexer never looks back at earlier characters; the state alone carries all it needs to know. That is the defining property of a finite automaton.

Example 2: a protocol as a transition table

Real automata are usually written as a table mapping (state, input) to the next state. Below is a simplified login session: three failed attempts lock the account.

flowchart LR
    A["Idle"] -->|"login ok"| B["LoggedIn"]
    A -->|"login fail"| C["OneFail"]
    C -->|"login fail"| D["TwoFails"]
    D -->|"login fail"| E["Locked"]
    C -->|"login ok"| B
    D -->|"login ok"| B
    B -->|"logout"| A

Three consecutive failed logins reach Locked, which has no outgoing edges.

Python A session state machine with a transition table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In scenario 2 the account reaches Locked, and the later ok event has no entry in the table, so it is ignored. Missing entries are one way to handle "impossible" input; the formal DFA in the next chapter will instead require a rule for every input in every state.

Limits of this approach

A finite state machine has only finitely many situations to remember, so it cannot track unbounded information such as "the nesting depth of brackets" or "how many items are in the cart". For those jobs you need a stack or counter, which leads to the pushdown automaton level of the Chomsky hierarchy. Next, we study the simplest machine on its own terms.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the lexer in a compiler recognize?

    Token classes like identifiers and numbers are regular languages, so a finite automaton can recognize them. Nesting is the parser's job.
  2. 2. Why is automaton-based string searching guaranteed to run in linear time?

    A DFA performs exactly one table lookup per input symbol, so total work is proportional to the text length.
  3. 3. Which task is beyond a plain finite state machine?

    Balanced parentheses require remembering an unbounded depth, which needs a stack, not a finite number of states.
  4. 4. In the session example, what happens to an 'ok' event in the Locked state?

    Locked has no outgoing transitions in the table, so the event is ignored.

Summary

  • Automata model anything with finitely many modes and a stream of inputs: lexers, search, protocols, UIs and circuits.
  • A transition table (state, input) to next state is the usual implementation.
  • Finite automata run in linear time with constant memory per step.
  • They cannot count without limit, which motivates stronger models like the pushdown automaton.

Next: Introduction to Finite Automata (DFA)