8
$\begingroup$

I consider pushdown automata on an alphabet $\Sigma$, which are intuitively finite automata with a stack. Formally, a pushdown automaton $A = (Q, q_0, F, \Gamma, \Delta)$ is a finite set $Q$ of states, an initial state $q_0 \in Q$, a subset $F \subseteq Q$ of final states, a stack alphabet $\Gamma$, and a set $\Delta$ of transitions of three kinds:

  • push transitions $(q, q', \gamma) \in Q\times Q \times \Gamma$ where you move from state $q$ to $q'$ while pushing $\gamma$ to the stack;
  • pop transitions $(q, \gamma, q') \in Q \times \Gamma \times Q$ where you are in state $q$, the top stack symbol is $\gamma$, and you remove it and move to state $q'$;
  • read transitions $(q, a, q') \in Q \times \Sigma \times Q$ where you move from state $q$ to state $q'$ while reading a letter $a$ and not touching the stack.

A run of $A$ on a word $w \in \Sigma^*$ is a sequence $(q_0, s_0, p_0), \ldots, (q_n, s_n, p_n)$ of configurations of $Q \times \Gamma^* \times \{0, \ldots, |w|\}$ such that $s_0$ is the empty stack, $p_0 = 0$, $p_n = |w|$, and every pair of configurations $(q_i, s_i, p_i), (q_{i+1}, s_{i+1}, p_{i+1})$ follows a transition, i.e., one of the following:

  • push: $(q_i, q_{i+1}, \gamma) \in \Delta$ and $s_{i+1} = s_i \gamma$ and $p_{i+1} = p_i$;
  • pop: $(q_i, \gamma, q_{i+1}) \in \Delta$ and $s_i = s_{i+1} \gamma$ and $p_{i+1} = p_i$;
  • read: $(q_i, a, q_{i+1}) \in \Delta$ and $s_i = s_{i+1}$ and $p_{i+1} = p_i+1$ and $w_{p_i} = a$.

The run is accepting if $q_n \in F$. We say that the automaton is unambiguous if, on every input word $w\in \Sigma^*$, there is at most one accepting run of the pushdown automata. It is well-known that pushdown automata can recognize the context-free languages, whereas unambiguous pushdown automata can recognize the strict subset of context-free languages that are not inherently unambiguous.

My question is about imposing weaker unambiguity requirements by only considering the sequence of the stack heights. Specifically, a height-unambiguous PDA is one where, for every word $w \in \Sigma^*$, the sequence of stack heights of an accepting run is unique. Formally, if $(q_0, s_0, p_0), \ldots, (q_n, s_n, p_n)$ and $(q_0', s_0', p_0'), \ldots, (q_{n'}', s_{n'}', p_{n'}')$ are accepting runs then $n = n'$ and $|s_i| = |s_i'|$ for every $0 \leq i \leq n$. A weakly height-unambiguous PDA obeys a weaker requirement: the sequence of stack heights at the read transitions is unique. Formally, writing $i_1 < \cdots < i_{|w|}$ and $i_1' < \cdots < i_{|w|}'$ the sequences of indices at which a read transition was taken, then $|s_{i_j}| = |s_{i_j'}'|$ for every $1 \leq j \leq |w|$.

My question is: Which context-free languages are recognized by weakly height-unambiguous PDAs? I can show with a bit of effort that every height-unambiguous PDA can be converted to an equivalent unambiguous PDA, via a variant of the determinization procedure for visibly pushdown automata, so height-unambiguous PDAs can express precisely the context-free languages that are not inherently unambiguous. But for weakly height-unambiguous I have no idea. Do you?

Intuitively, the weaker requirement allows the automaton to freely interact with its stack between reads, provided the size is the same at the reads. This allows the automaton to push and then pop stuff to the stack, but this is clearly unnecessary (the automaton can be normalized to shortcut those). However, it also allows the automaton to pop a large number of symbols and (non-deterministically) push other symbols back to go back to the same height (the rest of the word can then ensures that only reaching the correct height gives an accepting run). This does not seem very powerful (and usually you can get rid of it by using nondeterminism at the point where you started pushing the things that were later replaced), but I don't formally see how to normalize them away.

(Literature note: there is a notion of height-deterministic PDAs, which is related but stronger as it is an analogue of determinism not unambiguity. There is a notion of height-unambiguous PDAs, but the model is different (the automata are "real-time" and cannot push/pop an arbitrary number of states), and the expressiveness of the model is not discussed.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.