I am working through Linz and Rodger, An Introduction to Formal Languages and Automata (7th ed.), Chapter 1. This post is for coders who want the theoretical foundation of programming languages and parsers. I relate each concept to something you already write: regex, BNF, validators, state machines.
This post covers:
- The one idea the subject is about
- Mathematical preliminaries (sets, complement, products, partitions, functions, equivalence, induction, graphs)
- Languages and operations on them
- Grammars as BNF / parser rules
- Automata as validators (accepters) and transducers
- Where this shows up in compilers
- Cheat sheet and self-check
The one idea this whole subject is about
In everyday coding you write functions that look at text (or a stream of events) and decide yes/no:
isValidEmail(s) → true / false
matches(/^[0-9]+$/, s) → true / false
parseIdentifier(s) → accept / reject
doorController(events) → eventually "behaved correctly" or not
Theory packages that idea like this:
- Choose an alphabet = the allowed characters / event names (like a charset).
- A string = one finite sequence of those characters (like
"abc", or event listpress,open,close). - A language = the set of all strings that count as “yes”.
So:
A language is not a string.
A language is a collection (set) of strings: every input you would accept.
| Everyday | Theory word |
|---|---|
| The set of all valid emails | a language $L_{\text{email}}$ |
The set of all strings matching ^[0-9]+$ |
a language $L_{\text{digits}}$ |
| The set of event sequences that leave the door safe | a language $L_{\text{door}}$ |
One particular email "[email protected]" |
a string (Linz also calls it a sentence of that language) |
“Sentence of $L$” just means: a string that belongs to $L$. Weird word. Mentally replace it with “member of $L$” or “accepted string”.
L_digits = { "0", "1", "2", ..., "10", "11", ..., "999", ... } ← infinite set of strings
"42" is a sentence of L_digits because "42" ∈ L_digits
"4a" is NOT a sentence of L_digits because "4a" ∉ L_digits
Grammars and automata are two ways to describe such a set without listing it:
- Grammar ≈ generative rules (like a recursive descent grammar / BNF).
- Automaton ≈ a validator / recognizer: a state machine that reads a string and answers yes/no (same job as a regex engine or
isValid…()function). Linz’s word for this is accepter.
That is the chapter. Details below.
1.1 Mathematical preliminaries
Sets (you already use these)
A set is a bag of things with no duplicates and no order.
S = {0, 1, 2}
"is 1 in S?" → YES, because 1 ∈ S is true
"is 5 in S?" → NO, because 5 ∈ S is false
(equivalently: 5 ∉ S is true)
Coder view: like a Python set, or a SQL IN (...) list, or a TypeScript Set<T>.
| Write | Mean | Coder analogy |
|---|---|---|
| $S_1 \cup S_2$ | in either | s1 \| s2 |
| $S_1 \cap S_2$ | in both | s1 & s2 |
| $S_1 - S_2$ | in first, not second | s1 - s2 |
| $\emptyset$ | empty | set() |
| $\lvert S \rvert$ | how many elements | len(s) |
| $S_1 \subseteq S$ | every element of $S_1$ is also in $S$ | s1.issubset(s) |
Powerset $2^S$: the set of all possible subsets of $S$.
S = {a, b}
2^S = { ∅, {a}, {b}, {a,b} } ← 4 = 2² subsets
You will meet powersets again when converting NFA → DFA (each DFA state is a set of NFA states).
Complement: everything else, relative to a universe
Complement of $S$ = all things that are not in $S$, taken from an agreed universe $U$.
Without a universe, “not in $S$” is meaningless (not in $S$ among what?).
Universe U = {0,1,2,3,4,5,6,7,8,9} ← "all digits"
S = {0, 2, 4, 6, 8} ← even digits
complement of S = U − S = {1, 3, 5, 7, 9}
Notation: $\overline{S}$ or $U - S$.
For languages, the universe is almost always $\Sigma^*$ (all possible strings over the alphabet). So:
\[\overline{L} = \Sigma^* - L\]That is every possible string, minus the ones in $L$.
Example:
Σ = {0, 1}
Σ* = { λ, 0, 1, 00, 01, 10, 11, 000, ... } ← EVERY binary string, including empty
L = { strings that are only 0's } = { λ, 0, 00, 000, ... }
complement L̄ = Σ* − L
= { every binary string that contains at least one 1 }
= { 1, 01, 10, 11, 001, 010, ... }
So $\Sigma^* - L$ literally means: start from the set of all strings, remove the ones that are in $L$. What is left is the complement.
DeMorgan: NOT of OR / NOT of AND
In code / boolean logic you already know:
!(A || B) === (!A) && (!B)
!(A && B) === (!A) || (!B)
DeMorgan is the same fact for sets, with:
- $\cup$ playing the role of
|| - $\cap$ playing the role of
&& - complement $\overline{\,\cdot\,}$ playing the role of
!
Tiny example
U = {1,2,3,4,5}
A = {1,2}
B = {2,3}
A ∪ B = {1,2,3}
complement of (A ∪ B) = {4,5}
complement A = {3,4,5}
complement B = {1,4,5}
(complement A) ∩ (complement B) = {4,5} ← same
Know it as: set-NOT distributes like boolean-NOT.
Cartesian product: all ordered pairs
\[S_1 \times S_2 = \{ (x,y) : x \in S_1,\ y \in S_2 \}\]Coder view: nested loops; every combination; a tuple type [A, B].
Example 1: small
S1 = {red, blue}
S2 = {S, M}
S1 × S2 = {
(red, S), (red, M),
(blue, S), (blue, M)
}
Example 2: order matters
S1 = {2, 4}
S2 = {2, 3}
S1 × S2 contains (4, 2) ✓
S1 × S2 does NOT contain (2, 4):
first component 2 ∈ S1, second 4 ∉ S2, so (2,4) ∉ S1 × S2
Also (2,2) ≠ (2). Pairs are ordered: first slot from S1, second from S2.
Example 3: coding
users = {"alice", "bob"}
roles = {"admin", "viewer"}
pairs = {(u, r) for u in users for r in roles}
# { (alice,admin), (alice,viewer), (bob,admin), (bob,viewer) }
Example 4: why theory cares
A transition in an FSA is basically keyed by a pair $(\text{state}, \text{symbol})$.
The set of all such keys lives in $Q \times \Sigma$.
Partition: non-overlapping nonempty blocks that cover the set
A partition of $S$ is a family of subsets such that:
- every element of $S$ is in exactly one block
- no block is empty
- the union of the blocks is $S$
S = {1, 2, 3, 4, 5, 6}
OK partition: { {1,2}, {3}, {4,5,6} }
↑ nonempty ↑ no overlap ↑ union = S
NOT a partition: { {1,2}, {2,3}, {4,5,6} } ← 2 appears twice (overlap)
NOT a partition: { {1,2}, {3,4,5,6}, ∅ } ← empty block forbidden
NOT a partition: { {1,2}, {3} } ← 4,5,6 missing (does not cover S)
“Nonempty” means: you are not allowed to include the empty set as one of the blocks. Each block contains at least one element.
Equivalence relations (next) always produce a partition: each block = one equivalence class.
Functions $f : S_1 \to S_2$: typed functions
Read $f : S_1 \to S_2$ like a TypeScript / Java signature:
f: S1 → S2
means:
- inputs come from $S_1$ (domain)
- outputs live in $S_2$ (codomain)
- each input maps to exactly one output (that is what makes it a function)
S1 = {1, 2, 3}
S2 = {a, b}
f = { (1,a), (2,a), (3,b) } ← OK function: every input once
NOT a function: { (1,a), (1,b), (2,a) } ← 1 maps to two things
Coder analogies:
function square(n: number): number { return n * n } // total function on numbers you care about
function head(xs: T[]): T // PARTIAL if empty list is allowed: undefined for []
- Total on $S_1$: defined for every element of $S_1$.
- Partial: defined only for some of $S_1$ (missing cases = crash / undefined).
A relation is the looser thing: an input may relate to several outputs (like a multimap, or SQL join results).
Equivalence relations: same group as
An equivalence $\equiv$ is a rule for saying “$x$ and $y$ count as the same (for this purpose)”.
It must obey three properties:
| Word | Formal | Plain English | Check on “same age in years” |
|---|---|---|---|
| Reflexive | $x \equiv x$ | everything is equivalent to itself | Alice is the same age as Alice ✓ |
| Symmetric | $x \equiv y \Rightarrow y \equiv x$ | order does not matter | if A same age as B, then B same age as A ✓ |
| Transitive | $x \equiv y$ and $y \equiv z \Rightarrow x \equiv z$ | it chains | if A~B and B~C then A~C ✓ |
Classic example (Linz):
$x \equiv y$ iff $x \bmod 3 = y \bmod 3$ (same remainder mod 3).
2 ≡ 5 ≡ 8 ≡ 11 ≡ ... (all leave remainder 2)
0 ≡ 3 ≡ 6 ≡ 12 ≡ ... (remainder 0)
1 ≡ 4 ≡ 7 ≡ ... (remainder 1)
These three buckets partition the integers.
Non-example: “$x \lt y$” on numbers is not an equivalence. Not reflexive ($x \lt x$ false), not symmetric.
Induction: one concrete example
Claim: for every integer $n \ge 1$,
\[1 + 2 + \cdots + n = \frac{n(n+1)}{2}\]Basis ($n=1$): left side $1$, right side $\frac{1\cdot2}{2}=1$. OK.
Inductive hypothesis: assume it works for some $k \ge 1$:
\[1+2+\cdots+k = \frac{k(k+1)}{2}\]Inductive step: prove it for $k+1$:
\[\begin{align*} 1+\cdots+k+(k+1) &= \frac{k(k+1)}{2} + (k+1) \\ &= (k+1)\left(\frac{k}{2} + 1\right) \\ &= (k+1)\frac{k+2}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{align*}\]Done. So it holds for all $n \ge 1$.
Why theory books use this: many claims about strings/grammars are “true for length 0/1, and if true for shorter strings then true for this string”. Same pattern as the sum formula.
Contradiction (brief): to show $\sqrt{2}$ is irrational, assume it is $p/q$ in lowest terms, derive that both $p$ and $q$ are even, contradiction. Useful background; not central for the automata chapters.
Graphs (only what you need for state diagrams)
Circles + arrows. That is an FSA picture.
stateDiagram-v2
direction LR
[*] --> q0
q0 --> q1: a
q1 --> q1: b
- vertices = states
- directed edges = transitions
- edge label = symbol read (or event)
- a loop = arrow from a state to itself
You already know this if you have drawn Redux flows, game AI states, or TCP state diagrams.
1.2 Languages, with examples for every operation
Alphabet, string, language
Alphabet Σ = {a, b} ← like the charset { 'a', 'b' }
Some strings over Σ:
λ empty string (Linz). Some texts write ε. Same as "".
a
b
ab
baab
...
Σ* = { λ, a, b, aa, ab, ba, bb, aaa, ... } ← ALL finite strings over Σ
Σ+ = Σ* without λ ← ALL nonempty ones
Language $L$ = any subset of $\Sigma^*$.
So $L$ is a set of strings, never “one string”.
Example A: finite language
L_hi = { "hi", "hello" }
sentences of L_hi: "hi", "hello"
"hey" is not a sentence of L_hi
Example B: infinite language (pattern)
L_ab = { a^n b^n : n ≥ 0 }
= { λ, ab, aabb, aaabbb, ... }
"aabb" ∈ L_ab ✓ sentence
"abb" ∉ L_ab ✗ (two b's but only one a)
Operations on languages (same examples throughout)
Fix:
Σ = {a, b}
L1 = { a, ab }
L2 = { b, ba }
Union $L_1 \cup L_2$: strings in either:
{ a, ab, b, ba }
Intersection $L_1 \cap L_2$: in both:
∅ (nothing in common)
Difference $L_1 - L_2$: in $L_1$ but not $L_2$:
{ a, ab }
Complement $\overline{L_1} = \Sigma^* - L_1$:
every string over {a,b} EXCEPT "a" and "ab"
includes: λ, b, aa, ba, bb, aaa, aba, ...
Reverse $L_1^R = { w^R : w \in L_1 }$:
"a"^R = "a"
"ab"^R = "ba"
so L1^R = { a, ba }
Concatenation $L_1 L_2 = { xy : x \in L_1,\ y \in L_2 }$
(glue any string from $L_1$ in front of any string from $L_2$):
a + b = ab
a + ba = aba
ab + b = abb
ab + ba = abba
L1 L2 = { ab, aba, abb, abba }
Star $L_1^*$: think regex …*, but the unit you may repeat is any whole string from $L_1$, not a single character.
You already know: in regex, a* means “zero or more a’s” → "", "a", "aa", "aaa", …
Here $L_1 = { a,\ ab }$. So $L_1^*$ means: glue zero or more pieces end-to-end, and each piece must be either "a" or "ab".
Build it by how many pieces you use
0 pieces: glue nothing → only the empty string:
L1^0 = { λ } // like ""
1 piece: just pick one member of $L_1$:
L1^1 = L1 = { a, ab }
2 pieces: pick a first member, then a second, concatenate (L1 L1):
first \ second | a ab
---------------+------------------
a | a+a=aa a+ab=aab
ab | ab+a=aba ab+ab=abab
L1^2 = { aa, aab, aba, abab }
3 pieces: same idea, longer (e.g. a+a+a = aaa, a+ab+a = aaba, …). That set is $L_1^3$.
Star = all of those together:
\[L_1^* = L_1^0 \cup L_1^1 \cup L_1^2 \cup L_1^3 \cup \cdots\]So $L_1^*$ contains, among others:
λ (0 pieces)
a, ab (1 piece)
aa, aab, aba, abab (2 pieces)
aaa, aaab, aaba, … (3 pieces)
…
Quick membership tests
"aab" ∈ L1* ? YES : pieces a + ab
"abab" ∈ L1* ? YES : pieces ab + ab
"b" ∈ L1* ? NO : no way to build a lone "b" from only "a" and "ab"
"ba" ∈ L1* ? NO : would need a piece starting with b; L1 has none
Picture:
L1* = (nothing)
or [a|ab]
or [a|ab][a|ab]
or [a|ab][a|ab][a|ab]
or …
Same pattern as regex (a|ab)*.
Positive closure $L_1^+$ = same but at least one piece:
\[L_1^+ = L_1^1 \cup L_1^2 \cup L_1^3 \cup \cdots\]So $L_1^+$ is $L_1^*$ without the free empty string from “0 pieces” (here $\lambda \notin L_1^+$, because you cannot get $\lambda$ from one or more of "a" / "ab").
Tiny regex bridge
You already know regex. Formal languages are the maths under that:
| Regex | Language idea |
|---|---|
a\|b |
union |
ab |
concatenation |
a* |
star |
[^...] style “everything but” |
related to complement (careful: regex “complement” is messy; theory complement is $\Sigma^*-L$) |
1.2 Grammars: BNF / parser rules
If you have seen BNF, ANTLR, peg, or even a recursive-descent parser, you already know grammars.
Programming-shaped example: a tiny identifier
English rules:
- An id starts with a letter.
- Then zero or more letters or digits.
BNF / grammar form (same as Linz, just with angle-name variables):
<id> → <letter> <rest>
<rest> → <letter> <rest> | <digit> <rest> | λ
<letter> → a | b | c | ... | z
<digit> → 0 | 1 | ... | 9
Coder reading:
| Theory | Coding |
|---|---|
variables / nonterminals <id>, <rest> |
helper rules / nonterminal names |
terminals a,0,… |
actual characters in the source |
start symbol <id> |
the rule you call first |
production → |
“can be rewritten as” |
| derive until only terminals | parse / expand until concrete text |
One derivation of a0:
<id>
⇒ <letter> <rest>
⇒ a <rest>
⇒ a <digit> <rest>
⇒ a 0 <rest>
⇒ a 0 λ
= a0
The language of this grammar = the set of all strings you can derive this way = all legal ids.
Again: the language is the set; a0 is one sentence in that set.
Linz’s classic abstract grammar (same mechanism)
\[S \to aSb \mid \lambda\]S
⇒ aSb
⇒ aaSbb
⇒ aa λ bb
= aabb
Language = ${ a^n b^n : n \ge 0 }$ = balanced as then bs.
Same kind of object as the identifier language: just a different rule set.
Formal definition
Grammar $G = (V, T, S, P)$:
- $V$ = nonterminals (
<id>,S, …) - $T$ = terminals (characters)
- $S$ = start
- $P$ = list of productions
Two grammars are equivalent if they generate the same set of strings (like two parsers accepting the same language).
1.2 Automata: a validator/recognizer (or a transformer) with states
Job 1: validate / recognise a string (Linz: “accepter”)
You already write these:
isValidId("a0") → true
regex.test("42") → true / false
"does this event sequence leave the door safe?" → yes / no
An automaton doing that job is a validator (coder word) or recognizer (theory word). Linz calls it an accepter: it only answers accept or reject. It does not rewrite the input into something else.
Coder view of the loop:
state = START
for symbol in input:
state = next(state, symbol)
return state in ACCEPTING_STATES // yes or no
Job 2: transform while reading (Linz: “transducer”)
Same state-machine idea, but it also emits outputs as it goes (streaming encoder, motor commands). A Moore machine is this flavour: each state has an output (OPEN / OFF / CLOSE).
| Word you’ll see | Means |
|---|---|
| validator / recognizer / accepter | input → yes/no |
| transducer | input → outputs along the way |
| Deterministic | next(state, symbol) returns one next state |
| Nondeterministic | may return a set of possible next states |
| Configuration | snapshot: state + input position (+ storage) |
| Move | one step of the loop |
Finite automata = validator/recognizer with no unbounded extra memory: only the finite state.
flowchart LR
IN["input string"] --> SM["finite state machine"]
SM --> Y["accept = in the language"]
SM --> N["reject = not in the language"]
1.3 Applications (Linz’s motivation, in coder words)
- Grammar for C identifiers: BNF for names.
- Validator/recognizer (accepter) for C identifiers: state machine that accepts the same set.
- Serial adder as transducer: states remember carry; outputs sum bits.
Compilers literally do (1)+(2): grammar defines the language; automata/parsers recognise it.
Cheat sheet
Σ alphabet (charset / event names)
string one finite sequence (like "ab")
λ or ε empty string ""
Σ* all strings over Σ
L ⊆ Σ* a LANGUAGE = a SET of strings
sentence of L just means: a string that is in L
Σ* − L complement = all strings except those in L
L1 L2 concat all pairs
L* zero or more concatenations from L
grammar generative rules (BNF)
automaton state machine: validator/recognizer (accepter) or transducer
Self-check (use examples, not slogans)
- Give a language $L$ with exactly three sentences. Name one string that is not a sentence of $L$.
- With $\Sigma={0,1}$ and $L={0,00}$, write three strings in $\overline{L}$.
- With $L_1={a}$, $L_2={b}$, write $L_1 L_2$ and $L_1^*$.
- Explain reflexive / symmetric / transitive using “same Git branch name” or invent your own.
- Write a tiny grammar (BNF) for integers like
0,42,7(digits, no sign). Derive42.
Answers
1. One finite language with three sentences:
\[L = \{\text{hi},\ \text{hey},\ \text{yo}\}\]Sentences of $L$: "hi", "hey", "yo".
Not a sentence: "hello" (or $\lambda$, or "h", …).
2. $\overline{L} = \Sigma^* - L = {0,1}^* - {0,00}$.
Any three strings that are not "0" or "00" work, for example:
λ, 1, 01
(Also fine: 10, 11, 000, …)
3. Concatenation and star:
\[L_1 L_2 = \{ ab \}\] \[L_1^* = \{ a \}^* = \{ \lambda,\ a,\ aa,\ aaa,\ \ldots \}\]4. Let $x \equiv y$ mean “$x$ and $y$ are the same Git branch name” (string equality on the name).
| Property | Check |
|---|---|
| Reflexive | main ≡ main: every branch name equals itself. |
| Symmetric | if feature/foo ≡ feature/foo, the reverse holds too (equality is symmetric). |
| Transitive | if A’s checkout name equals B’s, and B’s equals C’s, then A’s equals C’s. |
So same-branch-name is an equivalence.
Counterexample that fails: “$x$ is a parent of $y$ in the commit graph” is not reflexive and not symmetric.
5. One grammar for unsigned digit strings (no leading-zero rule; 07 is allowed):
<int> → <digit> <rest>
<rest> → <digit> <rest> | λ
<digit> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Derivation of 42:
<int>
⇒ <digit> <rest>
⇒ 4 <rest>
⇒ 4 <digit> <rest>
⇒ 4 2 <rest>
⇒ 4 2 λ
= 42
Language of this grammar = ${0,1,\ldots,9}^+$ (all nonempty digit strings).