Regular expressions and finite automata

Alphabets, strings, and languages

Definition. An alphabet Σ is a finite nonempty set of symbols. A string is a finite sequence of symbols from Σ; the empty string is ε and has length zero. A language over Σ is any subset of Σ*.

Example. For Σ={0,1}, the set of all strings with exactly two 1s is a language: {0^i 1 0^j 1 0^k : i,j,k≥0}.

Exam point. ε is a string, while ∅ is a language with no strings; {ε} contains one string and differs from both.

Solved examples

Example 1 — concatenation. Let A={ε,0} and B={1,10}. Find AB.

1. Concatenate each member of A with each member of B.
2. ε·1=1 and ε·10=10.
3. 0·1=01 and 0·10=010.
4. AB={1,10,01,010}.

Example 2 — language powers. If L={a,bb}, list L² and decide whether ε belongs to L⁰.

1. L² contains aa, abb, bba, and bbbb.
2. By definition L⁰={ε}, regardless of whether ε is in L.
3. Answer: L²={aa,abb,bba,bbbb}; ε∈L⁰.

Regular expressions and their meaning

Definition. Over Σ, ∅, ε, and each symbol a∈Σ are regular expressions. If r and s are expressions, then (r|s), rs, and r* denote union, concatenation, and zero-or-more repetition. Precedence is star, concatenation, then union unless parentheses override it.

Example. (0|1)*01 denotes all binary strings ending in 01.

Exam point. Star permits zero repetitions, so r* always contains ε, even if r denotes ∅.

Solved examples

Example 1 — parse an expression. Describe a(b|c)*.

1. The initial a is required.
2. After it, choose any number of symbols, each independently b or c.
3. Zero choices are permitted, so a itself is included.
4. Language: strings beginning with a and followed only by b/c symbols.

Example 2 — exact suffix. Write an expression over {0,1} for strings whose final two symbols are 10.

1. The prefix before the suffix may be any binary string: (0|1)*.
2. Append the required suffix 10.
3. Expression: (0|1)*10.

Example 3 — at least one a. Give an expression over {a,b} for strings containing at least one a.

1. An arbitrary prefix is (a|b)*.
2. Choose one required a.
3. Allow any suffix (a|b)*.
4. Expression: (a|b)*a(a|b)*.

Example 4 — exact count. Write an expression for binary strings with exactly two 1s.

1. Any number of zeros may occur before the first 1: 0*.
2. A required 1 separates the first zero run from a second zero run.
3. Repeat for the second 1 and allow a final zero run.
4. Expression: 0*10*10*.

Finite automata and acceptance

Definition. A DFA is a tuple (Q,Σ,δ,q₀,F) with finite states Q, start state q₀, final states F, and a total transition function δ:Q×Σ→Q. Extend δ to strings by δ*(q,ε)=q and δ*(q,wa)=δ(δ*(q,w),a); a string is accepted iff δ*(q₀,w)∈F.

Example. A two-state DFA can accept binary strings with an even number of 1s by toggling on 1 and staying on 0.

Exam point. A DFA must specify what happens for every state-symbol pair; an omitted transition is not an implicit rejection unless a sink is added.

Solved examples

Example 1 — parity table. Construct a DFA for an even number of 1s.

State	0	1	Accepting?
E	E	O	yes
O	O	E	no

1. Start in E because zero 1s is even.
2. Reading 0 does not change the count parity.
3. Reading 1 switches between E and O.
4. A string is accepted exactly when the final state is E.

Example 2 — trace input. Use the table above on 10110.

1. Start E; read 1: O.
2. Read 0: O; read 1: E.
3. Read 1: O; read 0: O.
4. Final state O, so reject; the string has three 1s.

Example 3 — divisibility by three. Build a DFA that accepts binary numerals divisible by 3, allowing leading zeros.

1. State r records the numeric value modulo 3.
2. Appending bit b changes remainder to (2r+b) mod 3.
3. Transition table:

Remainder state	0	1	Accepting?
R0	R0	R1	yes
R1	R2	R0	no
R2	R1	R2	no

4. Start R0; accept R0. The transition follows the positional-value update.

Example 4 — trace a long input. Classify 110 with the divisibility DFA.

1. Start R0; first 1 gives R1.
2. Next 1 gives R0.
3. Final 0 leaves R0.
4. Accept; binary 110 is 6, divisible by 3.

Nondeterministic finite automata

Definition. An NFA may have zero, one, or many next states for a state-symbol pair; an ε-NFA may also move without consuming input. It accepts a string if at least one computation path consumes the whole string and ends in a final state. NFAs and DFAs recognize exactly the regular languages.

Example. For strings over {0,1} containing substring 101, an NFA can guess which 1 begins the target substring.

Exam point. Acceptance is existential over paths; one rejecting branch does not cancel an accepting branch.

Solved examples

Example 1 — subset construction. An NFA has states {s,p,f}, start s, final f, with transitions: s on 0→{s,p}, s on 1→{s}, p on 1→{f}, and f on either symbol→∅. Convert the reachable subsets to a DFA, treating missing moves as empty.

1. Initial subset {s}. On 0 it reaches {s,p}; on 1 it reaches {s}.
2. From {s,p}, on 0 reach {s,p}; on 1 reach {s,f}.
3. {s,f} is accepting because it contains f. On 0 it reaches {s,p}; on 1 it reaches {s}.
4. Reachable DFA subsets are {s}, {s,p}, {s,f}; only {s,f} accepts.

DFA subset	0	1	Accept?
{s}	{s,p}	{s}	no
{s,p}	{s,p}	{s,f}	no
{s,f}	{s,p}	{s}	yes

Shortcut or trap. A subset is accepting if it contains at least one NFA final state.

Example 2 — ε-closure. Let ε transitions be p→q and q→r, with r final. If the NFA reaches p before reading a symbol, determine whether the current subset accepts.

1. ε-closure(p)={p,q,r}.
2. The closure contains r, a final state.
3. The current subset is accepting, even before another input symbol is read.

Converting regular expressions to automata

Definition. Thompson construction builds an ε-NFA compositionally: union branches from a new entry, concatenation links fragments, and star adds bypass and repeat ε edges. Subset construction then converts the NFA to a DFA.

Example. The expression a|b uses a new start with ε edges to separate a and b fragments, followed by a shared final state.

Exam point. Conversion may produce exponentially many DFA states in the expression/NFA size; determinization preserves the language, not necessarily the number of states.

Solved examples

Example 1 — expression ab*. Describe a Thompson-style NFA behavior.

1. The initial a-fragment must be traversed once.
2. The b-star fragment has an ε bypass, so zero b symbols are allowed.
3. Its repeat edge allows any positive number of b symbols.
4. Accepted strings are a, ab, abb, and so on.

Example 2 — expression equivalence. Show that a(a|b)* describes strings over {a,b} beginning with a.

1. The first a is forced by concatenation.
2. The starred union allows any finite continuation of a/b symbols.
3. No other symbols or empty prefix before the first a are possible.
4. The described language is exactly all nonempty strings over {a,b} whose first symbol is a.

Product automata and Boolean combinations

Definition. Given complete DFAs A and B over the same alphabet, the product has state pairs and transitions componentwise. Choosing accepting pairs by Boolean rules recognizes union, intersection, and difference; complement flips final/nonfinal status for a complete DFA.

Example. Pair (p,q) accepts an intersection iff p and q are both final.

Exam point. Complementing an incomplete DFA without first completing it can give an incorrect language.

Solved examples

Example 1 — intersection of parity conditions. Build the state meaning for strings with an even number of 0s and an odd number of 1s.

1. Use pairs (p0,p1) where each component stores one parity bit.
2. There are four possible pairs.
3. Reading 0 toggles only the first bit; reading 1 toggles only the second.
4. Only pair (even,odd) is accepting.

Example 2 — complement. A complete DFA over {a,b} accepts strings ending in a. Describe its complement.