∴ discrete.

STEP-BY-STEP LESSON · §12.2

Finite-State Automata

Trace a string through a deterministic finite automaton.

Before you begin

Words, alphabet and empty word

An alphabet is a finite set of allowed symbols. A word is a finite sequence of them; order and repetitions matter. ε is the empty word, with length 0. The language {ε} contains one word, whereas ∅ contains none.

More in lesson §12.1Alphabet, empty word and length
Function, domain and codomain

A function assigns exactly one permitted output to every input in its domain. Its codomain is the declared output set; some members of that set may never be reached. The same formula on another domain or codomain can have different properties. f(x) names the output at x; it is not multiplication.

More in lesson §7.1FunctionFunction evaluation

Symbols

δ(q,a)
next state after symbol a in state q
Definitions and notation for this topic
DFA transition and acceptance
δ:Q×Σ→Q; δ(q,a); q₀; F⊆Q

A deterministic finite automaton has a finite state set Q, alphabet Σ, one initial state q₀, accepting states F⊆Q, and a transition δ(q,a) for each state-symbol pair. The transition gives the next state.

A word is accepted if and only if the state after its entire input lies in F. ε is accepted exactly when q₀∈F. An accepting state is not necessarily a halt state.

Separate glossary example

To accept binary words with an even number of 1s, use states E,O, start E, accept E. Reading 1 toggles E↔O; reading 0 leaves the state unchanged.

Open glossary card

Step by step

Step 1 / 6

Specify the machine

Specify states, an alphabet, a start state, accepting states, and a transition for every symbol from every state.

A complete DFA determines each next step uniquely.

Worked example

A DFA tracks parity of the number of 1s: E starts and accepts; O rejects. A 1 toggles E↔O; a 0 leaves the state unchanged. Trace 101.

  1. Start in E before reading any symbol; the input symbols in order are 1,0,1.
  2. From E, a 1 moves to O. A 0 leaves us in O.
  3. The last 1 returns to E; the string is accepted because it contains two 1s.

Follow a finite automaton

This machine checks whether a sequence of 0s and 1s contains an even number of 1s. It reads symbols; it does not calculate a binary number.

E means even, O means odd. Reading 0 keeps the state; reading 1 switches it. ε means an empty sequence, not the letter E.

Loaded sequence: 101

Reading is not finished. The current state describes the prefix read so far; the whole sequence is accepted only if reading ends in E.

Current state: E · 0/3
Consumed prefix: ε ▏ Unread suffix: 101

Start110EAccepting0ONonaccepting

Double circle: accepting state. Outer dashed ring: current state. Heavy arrow: last consumed transition.

Machine definition

δ(E,0)=E; δ(E,1)=O; δ(O,0)=O; δ(O,1)=E.

E: Even number of 1s read

O: Odd number of 1s read

    Optional self-check

    A DFA starts in rejecting S. Any 1 sends either state to accepting T; any 0 sends either state to S. Does input 10 accept?

    Show answer

    No. The run is S→T→S, and the final state rejects. Visiting T after a prefix does not settle acceptance.

    Source / textbook · approved access required

    Open source: printed p. 841 · PDF 865