1. Sets of Strings
Definition 1 — Concatenation
For : .
Example: ,
- ⚠️ In general .
Powers
, .
Example:
- ,
Definition 2 — Kleene closure
= all concatenations of arbitrarily many strings from (including ).
| Set | Kleene closure |
|---|---|
| (all bit strings) | |
| (even number of 1s) |
2. Finite-State Automata
Definition 3
A finite-state automaton (FSA) :
- — finite set of states
- — finite input alphabet
- — transition function
- — start state
- — final (accepting) states — drawn as double circles
(Singular: automaton; plural: automata.)
Example (Table 1 / Figure 1): , ,
| State | 0 | 1 |
|---|---|---|
| (final) | ||
| (final) |
Since both 0 and 1 take to , that edge is labeled “0,1”.
3. Language Recognition
Definition 4
- is recognized/accepted by if .
- = the language recognized by = set of all recognized strings.
- Two automata are equivalent if they recognize the same language.
Example (Figure 2):
| Automaton | Structure | Language |
|---|---|---|
| final loops on 1; a 0 goes to dead state | ||
final reached by 1 or 01; anything after → dead | ||
finals (loops on 0) and (reached by …10, then loops on 0,1) |
4. Designing Deterministic Finite-State Automata
An automaton is deterministic (DFA) when each (state, input) pair has a unique next state.
Design method: let each state remember a property of the input read so far; mark as final the states where the property you want holds. Use a dead (trap) state for strings that can never be accepted.
(a) Begin with two 0s — final:
| State | 0 | 1 | meaning |
|---|---|---|---|
| start | |||
| read “0” | |||
| began with 00 ✓ | |||
| dead |
(b) Contain two consecutive 0s — final:
| State | 0 | 1 | meaning |
|---|---|---|---|
| last symbol not 0 | |||
| last symbol 0 | |||
| 00 seen ✓ |
(c) Do NOT contain two consecutive 0s — finals:
Same machine as (b) with the final states complemented. (General trick: complementing in a DFA recognizes the complement language.)
(d) End with two 0s — final:
| State | 0 | 1 |
|---|---|---|
(A 1 always resets to .)
(e) Contain at least two 0s — final:
| State | 0 | 1 | meaning |
|---|---|---|---|
| zero 0s | |||
| one 0 | |||
| ≥ 2 zeros ✓ |
(f) Odd number of 1s AND end with at least two 0s — final:
Track two properties at once: parity of 1s × number of trailing 0s (0, 1, ≥2) ⇒ 6 states.
| State | # of 1s | trailing 0s | on 0 | on 1 |
|---|---|---|---|---|
| even | 0 | |||
| even | 1 | |||
| even | ≥ 2 | |||
| odd | 0 | |||
| odd | 1 | |||
| odd | ≥ 2 |
A 0 increases the trailing-zero count (capped at 2); a 1 flips parity and resets trailing zeros.
graph LR start(( )) --> s0 s0 -->|0| s1 s1 -->|0| s2 s2 -->|0| s2 s3 -->|0| s4 s4 -->|0| s5 s5 -->|0| s5 s0 -->|1| s3 s1 -->|1| s3 s2 -->|1| s3 s3 -->|1| s0 s4 -->|1| s0 s5 -->|1| s0 class s5 final classDef final stroke-width:4px
5. Equivalent Automata and Minimization
Example: show and are equivalent.
(finals ): , , , ; (dead, loops).
- Only
1reaches ; strings () reach . - = zero or more 0s followed by a final 1.
(final ): , , (dead).
- Must be some 0s then a single 1; all-zero strings stay in ; anything after the 1 goes to .
- ⇒ equivalent ✓
Machine minimization
- An FSA can have more states than an equivalent one; extra states waste hardware/software (e.g. in compilers).
- Machine minimization (Exercises 58–61) builds the equivalent automaton with the fewest states:
- First remove states unreachable from the start state.
- Merge equivalent states: two states are equivalent if every input string sends both to a final state or both to a non-final state. Replace states by their equivalence classes.
6. Nondeterministic Finite-State Automata (NFA)
Definition 5
A nondeterministic FSA is like a DFA except
— each (state, input) gives a set of possible next states (possibly empty).
- State table: list all possible next states.
- State diagram: an edge to every possible next state.
Recognition by an NFA
For : takes to a set ; takes each state of to a set — let be their union; continue. is accepted if the final set contains at least one final state.
Example: NFA with finals :
| State | 0 | 1 |
|---|---|---|
- is final and loops on 0 ⇒ accepts .
- is reached by or .
- .
Theorem 1 — NFA ⇒ DFA
If is recognized by a nondeterministic FSA, then is also recognized by a deterministic FSA.
Subset construction: each DFA state is a set of NFA states. Start with ; for each set and input, the next state is the union of the NFA moves. A DFA state is final if it contains any NFA final state.
Applied to the example above:
| DFA state | 0 | 1 | final? |
|---|---|---|---|
| ✓ | |||
| ✓ | |||
| ✓ | |||
| ✓ | |||
| ✓ | |||
| (dead) |