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 with $u$. The concept of a prefix can be further formalized as $v = ux$, where $x$ is a non-empty string ($x \neq \epsilon$) of the alphabet to which both strings $u$ and $v$ belong.

The usefulness of this property is obvious as it helps us realize that if we are trying to develop an elementary parser using a PDA for a given language that contains strings such as 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).