Massimo Caliman
by Massimo Caliman
~1 min read

Categories

  • Programming

Tags

  • Updated
  • computer-science
  • en
  • theory

Kleeneliness is next to Gödeliness

A language $L$ 1 cannot be deterministically recognized by empty stack 2 if there exist two distinct strings of $L$ such that one is a prefix of the other.

In more formal terms: if $\exists u, v \in L, u \neq v$, such that $v$ is prefixed by $u$. The concept of prefix can be further formalized as $v = ux$, where $x$ is a string $(\neq \epsilon)$ of the alphabet to which both strings $u$ and $v$ belong.

The usefulness of this property is obvious as it allows us to realize that if we are trying to develop an elementary parser using a PDA for a given language that contains strings of the type aabb and aabbbb, the automaton will stop, by empty stack, as soon as the prefix is consumed.

  1. This will be demonstrated in a future post. 

  2. So from a Deterministic Pushdown Automaton (DPDA).