Peter Linz Edition 5 Exercise 12.1 Question 9 (Page No. 308)

Question

$\text{Definition:}\space$A pushdown automaton $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ is said to be deterministic if it is an automaton as defined as defined, subject to the restrictions that, for every $q\in Q, a\in \Sigma \space\cup \{\lambda\}$ and $b \in \Gamma$

$1.$ $\delta (q,a,b)$ contains at most one element,

$2.$ if $\delta(q,\lambda,b)$ is not empty then $\delta(q,c,b)$ must be empty for every $c \in \Sigma$

Is the halting problem solvable for deterministic pushdown automata; that is, given a pda as in Definition, can we always predict whether or not the automaton will halt on input $w?$

Answer 1

Is the halting problem solvable for deterministic pushdown automata; that is, given a pda as in Definition 7.3, can we always predict whether or not the automaton will halt on input w?

Definition 7.3

A pushdown automaton

is said to be deterministic if it is an automaton as defined in Definition 7.1, subject to the restrictions that, for every q ∈ Q, a Σ ∪{λ} and b ∈ Γ, 1. δ(q, a, b) contains at most one element, 2. if δ (q, λ, b) is not empty, then δ (q, c, b) must be empty for every c ∈ Σ. The first of these conditions simply requires that for any given input symbol and any stack top, at most one move can be made. The second condition is that when a λ-move is possible for some configuration, no input-consuming alternative is available.