CS 121 › Lesson 10 of 12

Finite State Machines

Lesson 10 · OKSTEM College · AS Computer Science

What Is a Finite State Machine?

A Finite State Machine (FSM) — also called a Finite Automaton (FA) — is an abstract model of computation. It has a finite set of states, reads an input string symbol by symbol, and transitions between states according to a transition function.

ComponentSymbolMeaning
StatesQFinite set of configurations
AlphabetΣFinite set of input symbols
Transition functionδ: Q × Σ → QNext state given current state + input
Start stateq⊂0;Where the machine begins
Accept statesF ⊆ QStates that signal acceptance

DFA vs NFA

A Deterministic FA (DFA): exactly one transition per (state, symbol) pair. An NFA: may have zero, one, or many transitions — including ε-transitions (no input consumed). Both recognise the same class of languages: regular languages.

Key theorem: Every NFA can be converted to an equivalent DFA (subset construction). NFAs are easier to design; DFAs are easier to implement.

Regular Languages & Limits

Regular languages are closed under: union, intersection, complement, concatenation, Kleene star

Pumping Lemma: if a language is regular, long enough strings can be "pumped".
Used to PROVE languages are NOT regular.

Example non-regular language: L = {anbn | n ≥ 0}
(Requires counting — FSMs have no memory/stack.)

Practice Problems

1. Design an FSM over Σ={0,1} that accepts strings ending in "01".

States: q0 (start), q1 (saw '0'), q2 (saw '01' — accept).
Transitions:
δ(q0, 0) = q1, δ(q0, 1) = q0
δ(q1, 0) = q1, δ(q1, 1) = q2
δ(q2, 0) = q1, δ(q2, 1) = q0
Accept state: {q2}

2. Why can't a DFA recognise {a^n b^n | n ≥ 0}?

A DFA has finite memory (finitely many states). To match n a's with n b's requires counting n, which can be arbitrarily large. No finite set of states can track all possible values of n. The Pumping Lemma formalises this argument.

Knowledge Check

A DFA's transition function δ(q, a) returns

That's NFA; DFA returns exactly one next state.
Correct — DFA is deterministic: every (state, symbol) pair has exactly one defined transition.
The decision comes only after the full string is read.
Transitions may or may not change state, but the function always returns a (possibly same) state.
Recap: DFA = deterministic. δ(q, a) = q′ — exactly one arrow from each state for each input symbol.

An FSM accepts an input string if

NFAs can have missing transitions; the question is about the final state.
Correct — acceptance is determined only at the end of the input.
String length vs state count is irrelevant to acceptance.
Visiting an accept state mid-computation is not enough; must end there.
Recap: read the whole string, end in an accept state = ACCEPT. End in a non-accept state = REJECT.

NFAs and DFAs recognise

Theorem: NFA and DFA are equally powerful.
Correct — every NFA has an equivalent DFA (subset construction).
Context-free languages require pushdown automata (PDA), not FSMs.
Turing machines recognise all computable languages; FSMs are strictly weaker.
Recap: DFA ≡ NFA in expressive power. Both = regular languages. Pushdown automata = context-free. Turing machines = recursively enumerable.

The Pumping Lemma is used to

That's the subset construction algorithm.
Correct — it gives a contradiction if you assume a non-regular language is regular.
State minimisation uses a different algorithm (table-filling / Myhill-Nerode).
That's Thompson's construction.
Recap: Pumping Lemma is a proof tool for non-regularity. Assume L is regular, pump a long string, get a string that should be in L but isn't — contradiction.

The language {a^n b^n | n >= 0} is not regular because

Symbol count is unrelated.
Correct — FSMs have finite states; they can't count to arbitrary n.
Many infinite languages ARE regular (e.g., all strings of 0s and 1s).
Any finite number of states is allowed; the issue is that no finite number suffices.
Recap: FSMs have no stack, no memory beyond their current state. Matching a^n b^n requires remembering n — impossible with finitely many states.

← PreviousNext →