Pushdown Automata

We prove that L = {ww^R | w ∈ {a,b}*} cannot be recognized by any DPDA by contradiction.

Suppose there exists a DPDA M that recognizes L. Consider the strings anbnban and anbnaan for large n.

Both strings have the same prefix anbn. After reading this prefix, M must be in some configuration (q, γ) where q is the state and γ is the stack contents.

Since M is deterministic, from configuration (q, γ), the behavior on inputs ban and aan is completely determined. But anbnban ∉ L while we need M to accept strings of the form anbnbRan = anbn+1an when they are palindromes.

The key insight is that a DPDA cannot "know" where the middle of a palindrome occurs without being able to see the entire remaining input, which violates the finite-state constraint.

Therefore, no DPDA can recognize L, but an NPDA can recognize it by non-deterministically guessing the midpoint.

Given VPAs M₁ = (Q₁, Σ, Γ₁, δ₁, q₁⁰, Z₁⁰, F₁) and M₂ = (Q₂, Σ, Γ₂, δ₂, q₂⁰, Z₂⁰, F₂), we construct M = (Q, Σ, Γ, δ, q⁰, Z⁰, F) recognizing L(M₁) ∩ L(M₂).

Construction:

• Q = Q₁ × Q₂
• Γ = (Γ₁ × Γ₂) ∪ {Z⁰}
• q⁰ = (q₁⁰, q₂⁰)
• F = F₁ × F₂

Transition function: For a ∈ Σ_c (call symbols):

If δ₁((q₁, a, X₁)) = (p₁, Y₁) and δ₂((q₂, a, X₂)) = (p₂, Y₂), then δ((q₁, q₂), a, (X₁, X₂)) = ((p₁, p₂), (Y₁, Y₂)).

Similar constructions work for return and local symbols. The key insight is that since stack operations are input-driven, both automata perform the same stack operations synchronously, allowing us to track both computations in parallel.

Correctness: A string w is accepted by M if and only if the parallel simulation results in both M₁ and M₂ accepting, which occurs if and only if w ∈ L(M₁) ∩ L(M₂).

We prove EXPTIME-hardness by reduction from the acceptance problem for exponential-space Turing machines.

Given an exponential-space Turing machine T and input x, we construct a DPDA M such that the minimal DPDA equivalent to M has exponentially fewer states if and only if T accepts x.

Construction idea: The DPDA M simulates T on x using its stack to store the tape contents. If T accepts, then M has many "useless" states that can be merged during minimization. If T rejects, these states remain necessary.

The key insight is that the stack allows the DPDA to have exponentially many distinct configurations, each potentially corresponding to a different equivalence class in the minimal automaton.

Since determining whether T accepts x is EXPTIME-complete, and our reduction runs in polynomial time, DPDA minimization is EXPTIME-hard.

The EXPTIME upper bound follows from the fact that two DPDA states are equivalent if and only if they have the same future behavior on all possible stack contents, which can be checked in exponential time.

We construct a family of NPDAs that demonstrate the double-exponential lower bound.

For each n, consider the language L_n = {w#w^R | w ∈ {0,1}*, |w| ≤ 2^n} where # is a separator symbol.

NPDA construction: An O(n)-state NPDA can recognize L_n by:

1. Using n states to count the length of w (in binary)
2. Non-deterministically guessing when w ends and # begins
3. Pushing w onto the stack
4. After seeing #, popping and matching wR

DPDA lower bound: Any DPDA recognizing L_n must be able to distinguish between all possible prefixes of strings in L_n up to the # symbol.

There are 22n possible strings w of length at most 2n, and the DPDA must remember each one to verify the subsequent wR. Since the DPDA cannot guess where # occurs, it must track all possibilities simultaneously.

Using a fooling set argument, we can show that any DPDA requires at least 22n states to recognize L_n.

We prove that equivalence of deterministic PDAs is decidable by constructing an algorithm that determines whether L(M₁) = L(M₂) for DPDAs M₁ and M₂.

Algorithm outline:

1. Convert both DPDAs to equivalent CFGs G₁ and G₂ using the standard construction
2. Use the decidability of DPDA-CFG equivalence: construct a DPDA M' from G₂
3. Check if L(M₁) = L(M') using the DPDA equivalence algorithm

Core insight: For DPDAs, we can effectively compute a canonical form that allows comparison. The key lemma is:

Lemma: Two DPDA configurations (q₁, γ₁) and (q₂, γ₂) are equivalent if and only if for all strings w, the computations starting from these configurations have the same acceptance behavior.

This equivalence can be checked by constructing a finite automaton that tracks the "reachable configuration differences" between the two DPDAs. Since DPDAs are deterministic, this finite automaton has a bounded number of states.

Complexity: The algorithm runs in exponential time due to the conversion between DPDAs and CFGs, and the need to explore exponentially many configuration pairs.

Correctness: The algorithm terminates because the set of reachable configuration pairs is finite (up to stack equivalence), and it correctly identifies all cases where the DPDAs differ in their acceptance behavior.

We prove undecidability by reducing the Post Correspondence Problem (PCP) to NPDA equivalence.

PCP Instance: Given pairs (u₁, v₁), (u₂, v₂), ..., (uₙ, vₙ) where uᵢ, vᵢ ∈ Σ*, does there exist a sequence i₁, i₂, ..., iₖ such that uᵢ₁uᵢ₂...uᵢₖ = vᵢ₁vᵢ₂...vᵢₖ?

Construction: For each PCP instance, we construct NPDAs M₁ and M₂ such that L(M₁) = L(M₂) if and only if the PCP instance has no solution.

NPDA M₁: Accepts all strings of the form w#w where w ∈ Σ* and # is a separator symbol not in Σ.

NPDA M₂: Accepts:

1. All strings of the form w#w where w ∈ Σ*
2. All strings of the form uᵢ₁uᵢ₂...uᵢₖ#vᵢ₁vᵢ₂...vᵢₖ for any valid PCP sequence

Key insight: If the PCP has a solution, then M₂ accepts some strings that M₁ does not (specifically, the strings corresponding to PCP solutions where the u-part equals the v-part). If the PCP has no solution, then L(M₁) = L(M₂).

Correctness: The PCP instance has a solution if and only if L(M₁) ≠ L(M₂). Since PCP is undecidable, NPDA equivalence must also be undecidable.

Given a DPDA M = (Q, Σ, Γ, δ, q₀, Z₀, F), we construct a DPDA M' = (Q', Σ, Γ', δ', q₀', Z₀', F') such that L(M') = Σ* - L(M).

Key challenge: Unlike DFAs, we cannot simply flip the accepting states because a DPDA might reject a string by getting stuck (no valid transition) rather than reaching a non-accepting state.

Construction:

1. Completion: Add a sink state q_⊥ and transitions to make M total (never gets stuck)
2. State doubling: Create Q' = Q × {0, 1} ∪ {q_⊥} where the second component tracks whether we've seen the "end" of input
3. Endmarker simulation: Use the finite control to detect when input is exhausted
4. Acceptance flip: Accept in M' if and only if M would reject

Detailed construction:

• δ'((q, 0), a, X) = {((p, 0), α)} if δ(q, a, X) = (p, α)
• δ'((q, 0), ε, X) = {((q, 1), X)} (transition to "end-of-input" mode)
• F' = {(q, 1) | q ∉ F} ∪ {q_⊥}

Correctness: The construction ensures that M' accepts exactly when M rejects, handling both explicit rejection (reaching non-accepting state) and implicit rejection (getting stuck).

We prove that L₁ = {a^n b^n c^m | n, m ≥ 0} and L₂ = {a^n b^m c^m | n, m ≥ 0} are both deterministic context-free, but L₁ ∪ L₂ is not.

Step 1: L₁ is deterministic context-free.

DPDA for L₁: Push each a, pop for each b until balanced, then freely read any number of c's.

Step 2: L₂ is deterministic context-free.

DPDA for L₂: Freely read any number of a's, then push each b, pop for each c until balanced.

Step 3: L₁ ∪ L₂ is not deterministic context-free.

Suppose, for contradiction, that there exists a DPDA M recognizing L₁ ∪ L₂. Consider the string akbkck for large k.

This string is in both L₁ and L₂. However, after reading the prefix ak, the DPDA M must decide deterministically how to process the remaining bkck.

Dilemma: To accept strings in L₁, M should start matching a's with b's immediately. To accept strings in L₂, M should ignore the a's and start matching b's with c's.

Since M is deterministic, it cannot make both choices simultaneously. A formal proof shows that any DPDA attempting to recognize L₁ ∪ L₂ will fail on some inputs.

Let G be a CFG for L in Chomsky Normal Form with k variables. Set c = 22k and d = 2k.

Consider any string z ∈ L with |z| ≥ c and disjoint substrings u, v each of length at least d.

Parse tree analysis: Let T be a parse tree for z. Since |z| ≥ 22k, the tree T has height at least 2k.

Subtree identification: Let Tu and Tv be the minimal subtrees of T that contain the substrings u and v respectively. Since u and v are disjoint, Tu and Tv are also disjoint.

Variable repetition: Since each of Tu and Tv has yield of length at least 2k, each has height at least k. By the pigeonhole principle, there exist variables A and B that appear at least twice on some root-to-leaf paths in Tu and Tv respectively.

Interchange construction: The repeated variables allow us to "extract" the derivation patterns for generating substrings of the same length as u and v. By swapping these derivation patterns between the subtrees, we obtain strings u' and v' such that replacing u with u' and v with v' in z yields another string in L.

Formal interchange: If A ⇒* u1Au2 and A ⇒* u3 in Tu, and B ⇒* v1Bv2 and B ⇒* v3 in Tv, then we can construct derivations where the roles of these patterns are interchanged.

We use Ogden's lemma to prove that L = {a^i b^j c^k d^l | i = 0 or j ≠ k or k ≠ l} is not context-free.

Strategy: We'll show that the complement Lc = {a^i b^j c^k d^l | i > 0 and j = k and k = l} is not context-free, which implies L is not context-free (since CFLs are not closed under complement).

Actually, let's directly prove L' = {a^i b^j c^j d^j | i, j ≥ 1} is not context-free.

Proof: Assume L' is context-free with pumping constant p. Consider the string s = apbpcpdp.

Strategic marking: Mark all positions in the bpcpdp portion, leaving the a's unmarked. This gives us 3p marked positions.

By Ogden's lemma, s = uvwxy where vwx contains at most p marked positions and vx contains at least one marked position.

Case analysis: Since vwx has at most p marked positions and the marked region spans 3p positions across three different symbol types, vwx cannot span all three symbol types {b, c, d}.

Therefore, vx affects at most two of the three counts {|s|_b, |s|_c, |s|_d}. Pumping with i = 2 will increase at most two of these counts while leaving the third unchanged, violating the constraint that all three must be equal.

This contradicts the assumption that L' is context-free.