CS138 — Automata & Formal Languages

What is the difference between a set and a sequence?

A set has no order and no repeated elements ({1,2,3} = {3,2,1}); in a sequence, order matters and repetitions are allowed ((1,2,3) ≠ (3,2,1)).

For a function f: D → R, what are the domain and range?

The domain D is the set of possible inputs; the range is the subset of R consisting of values actually taken by f. Every input maps to exactly one output.

What three properties make a binary relation an equivalence relation?

Reflexive (aRa), symmetric (aRb implies bRa), and transitive (aRb and bRc implies aRc). Example: "has the same length as" on strings.

What is a directed graph, and how does it relate to automata?

A directed graph is a pair (V, E) where edges are ordered pairs of vertices. A DFA is essentially a directed graph whose edges are labeled with alphabet symbols.

Define: alphabet Σ, string, empty string ε, and Σ*.

An alphabet is a finite set of symbols; a string is a finite sequence of symbols from Σ; ε is the string of length 0; Σ* is the set of all finite strings over Σ.

What are the two steps of a proof by mathematical induction?

Basis: prove P holds for the smallest case (e.g., P(0)). Inductive step: assume P(k) for arbitrary k (the induction hypothesis) and prove P(k+1).

Give the formal 5-tuple definition of a DFA.

(Q, Σ, δ, q₀, F): Q is a finite set of states, Σ is the alphabet, δ: Q × Σ → Q is the transition function, q₀ ∈ Q is the start state, and F ⊆ Q is the set of accept states.

When does a DFA M accept a string w?

When the sequence of states obtained by following δ on the symbols of w, starting from q₀, ends in a state belonging to F. Otherwise M rejects w.

How is the transition δ(q, a) = r drawn in a state diagram?

As an arrow labeled "a" from state q to state r. The start state has an arrow pointing to it from nowhere; accept states are drawn as double circles.

What is a regular language?

A language recognized by some DFA — equivalently, by some NFA or described by some regular expression.

What does it mean to say a DFA M recognizes language A?

It means L(M) = A: M accepts exactly the strings in A and rejects all others.

What are the two key differences between an NFA and a DFA?

An NFA's transition function δ: Q × Σ_ε → P(Q) returns a set of states (possibly empty) instead of a single state, and it allows ε-transitions that consume no input symbol.

What is an ε-transition?

A transition labeled ε that a computation branch may take without reading an input symbol, allowing it to change state "for free."

When does an NFA accept its input string?

If any branch of its computation tree ends in an accept state after the entire input is consumed (ε-moves allowed). It rejects only if every possible branch rejects.

How does the subset construction convert an NFA into an equivalent DFA?

Each DFA state represents a subset of NFA states (including ε-closures). From subset R on symbol a, go to {q : q ∈ δ(r, a) for some r ∈ R}. The start state is the ε-closure of the NFA start; a subset is accepting if it contains any NFA accept state.

Why does every NFA have an equivalent DFA?

The subset construction simulates all NFA branches in parallel by tracking the set of possible current states as a single DFA state, so the DFA accepts exactly the same strings. Hence DFAs and NFAs recognize the same class: the regular languages.

What counts as a regular expression over Σ?

Built inductively: each a ∈ Σ, ε, and ∅ are regular expressions; if R₁ and R₂ are regular expressions, so are (R₁ ∪ R₂), (R₁ ∘ R₂), and (R₁*).

Write a regular expression for strings over {0,1} containing at least one 1.

(0 ∪ 1)1(0 ∪ 1) — any number of symbols, then a 1, then anything. Equivalently Σ1Σ.

How do you build an NFA for the concatenation R₁ ∘ R₂ from NFAs for R₁ and R₂?

Place them in series: add ε-transitions from every accept state of N₁ to the start state of N₂. The accept states of the new NFA are those of N₂.

State the theorem connecting regular expressions and finite automata.

A language is regular if and only if some regular expression describes it. Proved by converting REs to NFAs (inductive construction) and NFAs back to REs (GNFA state elimination).

Define the three regular operations on languages A and B.

Union: A ∪ B = {x : x ∈ A or x ∈ B}. Concatenation: A ∘ B = {xy : x ∈ A and y ∈ B}. Star: A* = {x₁x₂…xₖ : k ≥ 0 and each xᵢ ∈ A}.

Why are regular languages closed under union?

Given NFAs N₁, N₂ for A and B, build an NFA with a new start state and ε-transitions to both start states. It accepts exactly when either branch accepts, so it recognizes A ∪ B.