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 ).

SetKleene 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): , ,

State01
(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):

AutomatonStructureLanguage
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:

State01meaning
start
read “0”
began with 00 ✓
dead

(b) Contain two consecutive 0s — final:

State01meaning
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:

State01

(A 1 always resets to .)

(e) Contain at least two 0s — final:

State01meaning
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 1strailing 0son 0on 1
even0
even1
even≥ 2
odd0
odd1
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 1 reaches ; 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:
    1. First remove states unreachable from the start state.
    2. 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 :

State01
  • 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 state01final?
✓
✓
✓
✓
✓
(dead)