Nondeterministic Finite Automata (NFAs)

Proof of Extensivity: By definition, for any q ∈ S, we have q ∈ E(q). Therefore, S ⊆ ⋃q∈S E(q) = E(S).

Proof of Monotonicity: If S ⊆ T, then E(S) = ⋃q∈S E(q) ⊆ ⋃q∈T E(q) = E(T) since we're taking the union over a larger set.

Proof of Idempotence: We need to show E(E(S)) = E(S).

By extensivity, we know E(S) ⊆ E(E(S)).

For the reverse inclusion, we show that E(E(S)) ⊆ E(S). Let r ∈ E(E(S)). Then there exists p ∈ E(S) such that r ∈ E(p). This means there is a sequence of ε-transitions from p to r.

Since p ∈ E(S), there exists q ∈ S such that p ∈ E(q). This means there is a sequence of ε-transitions from q to p.

By concatenating these sequences, we get a sequence of ε-transitions from q to r, which implies r ∈ E(q) ⊆ E(S).

Therefore, E(E(S)) ⊆ E(S), and by the antisymmetry of set inclusion, E(E(S)) = E(S).

We prove that for any string w = w1w2...wn, there exists an accepting computation path r0, r1, ..., rn if and only if δ̂(q0, w) ∩ F ≠ ∅.

(⇒) Suppose there exists an accepting computation path r0, r1, ..., rn. We will prove by induction that ri ∈ δ̂(q0, w1w2...wi) for all i = 0, 1, ..., n.

Base case: i = 0. By definition of a computation path, r0 ∈ E(q0) = δ̂(q0, ε).

Inductive step: Assume ri-1 ∈ δ̂(q0, w1w2...wi-1) for some i ≥ 1. By definition of a computation path, ri ∈ E(δ(ri-1, wi)). Using the definition of the extended transition function:

δ̂(q0, w1w2...wi) = ⋃p∈δ̂(q0,w1w2...wi-1) E(δ(p, wi))

Since ri-1 ∈ δ̂(q0, w1w2...wi-1) and ri ∈ E(δ(ri-1, wi)), we have ri ∈ δ̂(q0, w1w2...wi).

By induction, rn ∈ δ̂(q0, w). Since the computation path is accepting, rn ∈ F. Therefore, rn ∈ δ̂(q0, w) ∩ F, which means δ̂(q0, w) ∩ F ≠ ∅.

(⇐) Suppose δ̂(q0, w) ∩ F ≠ ∅. Then there exists rn ∈ δ̂(q0, w) ∩ F. We need to construct an accepting computation path ending at rn.

By the definition of the extended transition function, there must exist a sequence of states r0, r1, ..., rn such that:

1. r0 ∈ E(q0)
2. ri ∈ E(δ(ri-1, wi)) for i = 1, 2, ..., n

This is precisely the definition of a computation path. Since rn ∈ F, this is an accepting computation path.

We prove that any NFA recognizing L = {w | w ends with ab} requires at least 2 states.

Suppose, for contradiction, that there exists an NFA M with just 1 state, q, that recognizes L. Since ab ∈ L, state q must be an accepting state.

Now consider the string a. Since a ∉ L, there should be no accepting computation path for a. However, with only one state q, after reading a, the NFA must be in state q (if it can process the string at all). Since q is an accepting state, the NFA would incorrectly accept a.

Therefore, any NFA recognizing L requires at least 2 states.

We prove that the language Ln = {w ∈ {a,b}*| the nth symbol from the end is a} can be recognized by an (n+1)-state NFA, but any DFA recognizing it requires at least 2ⁿ states.

NFA Construction: We can build an (n+1)-state NFA M = (Q, Σ, δ, q0, F) where:

• Q = {q0, q1, ..., qn}
• Σ = {a, b}
• q0 is the start state
• F = {qn}
• The transitions are:
  • δ(q0, a) = {q0, q1} (on a, either stay in q₀ or move to q₁)
  • δ(q0, b) = {q0} (on b, stay in q₀)
  • δ(qi, a) = δ(qi, b) = {qi+1} for i = 1, 2, ..., n-1 (advance through the counter states)

This NFA works by guessing the position of the n-th symbol from the end. When it reads an a, it nondeterministically guesses whether this is the critical position and starts counting the remaining n-1 symbols if so.

DFA Lower Bound: To prove that any DFA needs at least 2ⁿ states, we use a fooling set argument. Consider the set of strings S = {w ∈ {a,b}* | |w| = n-1}. There are 2^n-1 such strings.

For any two distinct strings u, v ∈ S, there must be a position where they differ. Without loss of generality, assume u has a and v has b at this position.

Now consider the suffix string z that, when appended to u or v, makes the differing position exactly n symbols from the end. Then uz ∈ Ln but vz ∉ Ln.

This means that after reading u and v, any DFA must be in different states, otherwise it couldn't distinguish between uz and vz. Since there are 2^n-1 strings in S, the DFA must have at least 2^n-1 states.

A more careful analysis using the full language definition shows that 2ⁿ states are actually necessary.

We prove that the DFA D constructed by the subset construction algorithm accepts exactly the same language as the original NFA N.

We will show that for any string w ∈ Σ*, δ'(q0', w) = δ̂(q0, w), where δ̂ is the extended transition function of the NFA.

Proof by induction on the length of w:

Base case: w = ε (the empty string)

δ'(q0', ε) = q0' = E({q0}) = δ̂(q0, ε)

Inductive step: Assume that for some string x ∈ Σ*, δ'(q0', x) = δ̂(q0, x). We need to show that for any symbol a ∈ Σ, δ'(q0', xa) = δ̂(q0, xa).

By the definition of δ':

δ'(q0', xa) = δ'(δ'(q0', x), a) = δ'(δ̂(q0, x), a) (by the induction hypothesis)

= E(⋃q∈δ̂(q0,x) δ(q, a)) (by the definition of δ')

By the definition of the extended NFA transition function:

δ̂(q0, xa) = E(⋃q∈δ̂(q0,x) δ(q, a))

Therefore, δ'(q0', xa) = δ̂(q0, xa).

By induction, for all w ∈ Σ*, δ'(q0', w) = δ̂(q0, w).

Now, w ∈ L(D) if and only if δ'(q0', w) ∈ F', which by definition of F' happens if and only if δ'(q0', w) ∩ F ≠ ∅. But δ'(q0', w) = δ̂(q0, w), so this is equivalent to δ̂(q0, w) ∩ F ≠ ∅, which means w ∈ L(N).

Therefore, L(D) = L(N).

We prove that the NFA N' constructed by the ε-elimination algorithm accepts exactly the same language as the original NFA N.

We will show that for any string w ∈ Σ* and any state q ∈ Q, δ̂'(q, w) = ⋃p∈E(q) δ̂(p, w), where δ̂ and δ̂' are the extended transition functions of N and N', respectively.

Proof by induction on the length of w:

Base case: w = ε (the empty string)

δ̂'(q, ε) = {q} (by definition of δ̂' for an NFA without ε-transitions)

⋃p∈E(q) δ̂(p, ε) = ⋃p∈E(q) E(p) = E(q) (by definition of δ̂ and E)

These are not equal in general. However, for the purpose of language recognition, we only care about acceptance, which depends on δ̂'(q0, w) ∩ F' for N' and δ̂(q0, w) ∩ F for N.

By definition of F', q ∈ F' if and only if E(q) ∩ F ≠ ∅. Therefore, {q} ∩ F' ≠ ∅ if and only if E(q) ∩ F ≠ ∅.

So for w = ε, δ̂'(q, w) ∩ F' ≠ ∅ if and only if E(q) ∩ F ≠ ∅, which is equivalent to δ̂(q, w) ∩ F ≠ ∅.

Inductive step: Assume that for some string x ∈ Σ* and for all q ∈ Q, δ̂'(q, x) ∩ F' ≠ ∅ if and only if ⋃p∈E(q) δ̂(p, x) ∩ F ≠ ∅.

We need to show that for any symbol a ∈ Σ, δ̂'(q, xa) ∩ F' ≠ ∅ if and only if ⋃p∈E(q) δ̂(p, xa) ∩ F ≠ ∅.

By the definition of δ̂':

δ̂'(q, xa) = ⋃r∈δ̂'(q,x) δ'(r, a)

= ⋃r∈δ̂'(q,x) ⋃s∈E(r) δ(s, a) (by the definition of δ')

By the definition of δ̂:

⋃p∈E(q) δ̂(p, xa) = ⋃p∈E(q) ⋃r∈δ̂(p,x) E(δ(r, a))

Through careful analysis and using the properties of ε-closures, we can show that δ̂'(q, xa) ∩ F' ≠ ∅ if and only if ⋃p∈E(q) δ̂(p, xa) ∩ F ≠ ∅.

Therefore, by induction, L(N') = L(N).

Given NFAs M1 = (Q1, Σ, δ1, q1, F1) and M2 = (Q2, Σ, δ2, q2, F2), we construct an NFA M = (Q, Σ, δ, q0, F) for L(M1) ∪ L(M2):

• Q = Q1 ∪ Q2 ∪ {q0} where q0 is a new start state
• δ combines δ1 and δ2, plus:
  • δ(q0, ε) = {q1, q2} (epsilon transitions to both original start states)
• F = F1 ∪ F2 (accept if either original NFA would accept)

This construction has |Q₁| + |Q₂| + 1 states and preserves the structure of both original NFAs.

Correctness: A string w is accepted by M if and only if there exists an accepting computation path from q0. From q0, the NFA can move to either q1 or q2 via ε-transitions, and then follow the computation in either M1 or M2. Thus, w is accepted by M if and only if w is accepted by either M1 or M2, which means w ∈ L(M1) ∪ L(M2).

Given NFAs M1 = (Q1, Σ, δ1, q1, F1) and M2 = (Q2, Σ, δ2, q2, F2), we construct an NFA M for L(M1) · L(M2):

• Q = Q1 ∪ Q2
• The start state is q1
• F = F2 if ε ∉ L(M1), otherwise F = F1 ∪ F2
• δ combines δ1 and δ2, plus:
  • For each q ∈ F1, add δ(q, ε) = δ(q, ε) ∪ {q2}

This construction has |Q₁| + |Q₂| states and creates ε-transitions from every accepting state of M1 to the start state of M2.

Correctness: A string w is in L(M1) · L(M2) if and only if w = xy where x ∈ L(M1) and y ∈ L(M2). In the NFA M, after reading x, the automaton can be in some accepting state of M1, from which it can move to q2 via an ε-transition and then process y according to M2. The special case for ε ∈ L(M1) ensures that if x can be empty, then w can be accepted solely by M2.

Given an NFA M = (Q, Σ, δ, q0, F), we construct an NFA M* for L(M)*:

• Q' = Q ∪ {q'0} where q'0 is a new start state
• The start state is q'0
• F' = F ∪ {q'0}
• δ' extends δ with:
  • δ'(q'0, ε) = {q0}
  • For each q ∈ F, add δ'(q, ε) = δ(q, ε) ∪ {q0}

This construction has |Q| + 1 states and allows for zero or more repetitions of strings in L(M).

Correctness: The new start state q'0 is accepting, which allows M* to accept the empty string (representing zero repetitions). For one or more repetitions, the NFA can move from q'0 to q0 via an ε-transition, process a string in L(M), reach an accepting state in F, and then either accept or move back to q0 to process another string in L(M). This precisely captures the behavior of the Kleene star operation.

We prove that the problem of determining if w ∈ L(M) for an NFA M is NL-complete.

NL-hardness: The PATH problem (determining if there is a path from vertex s to vertex t in a directed graph) is a known NL-complete problem. We can reduce PATH to NFA acceptance: given a graph G = (V, E) and vertices s, t, construct an NFA M = (V, {a}, δ, s, {t}) where δ(u, a) = {v | (u, v) ∈ E}. Then a ∈ L(M) if and only if there is a path from s to t in G.

NL algorithm: To determine if w ∈ L(M) for an NFA M = (Q, Σ, δ, q0, F) and string w = w1w2...wn, a nondeterministic Turing machine can:

1. Guess a sequence of states r0, r1, ..., rn
2. Verify that r0 = q0
3. For each i = 1, 2, ..., n, verify that ri ∈ δ(ri-1, wi)
4. Verify that rn ∈ F

This algorithm needs only logarithmic space to store the current and next state (which can be encoded in O(log |Q|) bits) and the current position in the input (which can be encoded in O(log |w|) bits).

Therefore, NFA acceptance is NL-complete.