Kleeneliness is next to Gödeliness A language L

^{1}`not`

can be deterministically recognised by empty stack^{2}if there exist two distinct strings of L such that one is prefixed by the other.

In more formal terms if ∃ u,v ∈ L : u is prefixed by v where the concept, of prefix can be further formalised as v = ux where x is a string of the alphabet to which both strings u and v belong.

The usefulness of this property is obvious as it allows us to realise that if we are wasting time 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.