Models of Computation MT23, Non-deterministic pushdown automata

A 7-tuple $(Q, \Sigma, \Gamma, \delta, q _ 0, \bot, F)$ where $Q, \Sigma, \Gamma, \delta, F$ finite sets and

• $Q$ is the set of states
• $\Sigma$ is the input alphabet
• $\Gamma$ is the stack alphabet
• $\delta : Q \times (\Sigma \cup \\{\epsilon\\}) \times \Gamma \to \mathcal P (Q \times \Gamma^\star)$
• $q _ 0 \in Q$ is the start state
• $\bot \in \Gamma$ is the initial stack symbol
• $F \subseteq Q$ is the set of accept states

A configuration $(q, w, v)$ of an NPDA is an element of $Q \times \Sigma^\star \times \Gamma^\star$ that describes

1. $q$, The current state
2. $w$, The portion of input word yet unread
3. $v$, The current stack contents

The next configuration relation $\to$ is defined as so:

• If $(q', \gamma) \in \delta(q, a, A)$ then for any $w \in \Sigma^\star$ and $v \in \Gamma^\star$, $(q, aw, Av) \to (q', w, \gamma v$), and
• If $(q', \gamma) \in \delta(q, \epsilon, A)$ then for any $w \in \Sigma^\star$ and $v \in \Gamma^*$, $(q, w, Av) \to (q', w, \gamma v)$.

Let $\to^\star$ be the reflexive and transitive closure of $\to$.

The language recognised by an NPDA accepting by final state is the set of strings $w$ such that $\exists q \in F$, $\gamma \in \Gamma^\star$ such that

The language recognised by an NPDA accepting by empty stack is the set of strings $w$ such that $\exists q \in Q$ such that

For some $q \in F$ and $y \in \Gamma^\star$ we have $(q _ 0, x, \bot) \stackrel{\star}{\to} (q, \epsilon, \gamma)$.

• Accept by final state, there exists a sequence of transitions using $x$ that lands in a final state
• Accept by empty stack, there exists a sequence of transitions that mean the stack is empty in some state.

• Pops a symbol of the stack
• Push a sequence of symbols (possibly $\epsilon$) onto the stack
• Move read head one cell to the right
• Enter a new state

An edge, joining a state labelled $q$ and $q'$, with edge label by $a, Z \to \gamma$.

Every NPDA can be simulated by a one-state NPDA.

Two states, stack alphabet is terminals, variables and $\bot$.

• Place the start variable onto the stack and move to next state
• Pop off the stack. There are three cases:
  • $x$ is a variable: nondeterministically replace by derivation for that variable
  • $x$ is a terminal: read the next input symbol and reject if it doesn’t match $x$
  • $x$ is $\bot$, accept (empty stack criterion)

High-level description:

• Push the input symbols onto the stack, one at a time.
• Non-deterministically guess that the middle of the string at some point during $1$, and then change to popping off the stack for each symbol read, checking to see if the symbols just popped off and just read are the same.
• If they are always the same symbols, and the stack empties at the same as the input is finished, accept.

We break down as follows:

• Every NPDA can be simulated by an NPDA with one state (which accepts by empty stack)
• Every NPDA with one state has an equivalent CFG.

Every NPDA with one state has an equivalent CFG: Take a one state NPDA that accepts by empty set

where:

• $\\{\star\\}$ is set of all states, in this case there is just one
• $\Sigma$ is the alphabet
• $\Gamma$ is the stack alphabet
• $\delta$ is the transition function
• $\star$ is the initial state, which is also just the only choice
• $\perp$ is the initial stack symbol
• $\emptyset$ is the set of accepting states (which is empty since we accept by empty stack)

and construct a CFG:

where for every transition

$R$ contains the rule

where $c$ is any element of $\Sigma \cup \\{\epsilon\\}$.

Every NPDA can be simulated by a one-state NPDA: The idea is to maintain all state information on the stack. Wlog we can assume that $M$ is of the form:

(defined in the same order as in the above section), and that $M$ empties its stack after entering the final state $t$.

Define $\Gamma' = Q \times \Gamma \times Q$ and use the notation $\langle p, A, q\rangle$ for its elements. We construct a new NPDA

that accepts by empty stack. Being explicit again:

• $\\{\star\\}$ is the set of all states, which in this case is just one
• $\Sigma$ is the alphabet
• $\Gamma'$ is the extended stack alphabet defined above
• $\delta'$ is a new transition function we will define in a moment
• $\star$ is the initial state (again, the only choice)
• $\langle s \perp t\rangle$ is the initial stack symbol
• $\emptyset$ is the set of accepting states, which is empty since we accept by final state

For each transition

where $c \in \Sigma \cup \\{\epsilon\\}$, include in $\delta'$ the transition

for all choices of $q _ 1, \cdots, q _ k$.

The intuitive idea is that $M'$ simulates $M$ guessing non-deterministically what state $M$ will be in at certain points in the computation, saving those guesses on the stack, and then verifying later that the guesses were correct.

We have the lemma:

$M'$ can scan a string $x$ starting with only $\langle p, A, q\rangle$ on its stack and end up with an empty stack if and only if $M$ can scan $x$ starting in state $p$ with only $A$ on its statck, and end up in state $q$ with an empty stack, i.e.

iff

Then this lemma justifies the correctness: $M'$ begins a computation with only $\langle s \perp t \rangle$ on its stack, where $s$ is the start state of $M$ and $t$ is the accepting state. By the lemma, $M'$ can scan the input $x$ and end up with an empty stack iff $M$ can scan the input $x$, starting in $s$ and ending up in $t$ with an emtpy stack. So it follows that $L(M) = L(M')$.