Some negative results concerning DPDA's (Q1058306)

Bekanntlich definiert ein DPDA eine Abbildung L: Für jede Konfiguration c ist L(c) die mit c als Start akzeptierte Sprache. \(c_ 1\) und \(c_ 2\) heißen äquivalent genau dann, wenn \(L(c_ 1)=L(c_ 2)\) gilt. Die Arbeit ist eine Warnung davor, die Komplexität von L zu unterschätzen. Unter anderem wird gezeigt: Die Menge \(\{\) \(c|\) L(c) ist regulär\(\}\) ist im allgemeinen nicht kontextfrei. Die Äquivalenzklasse einer Konfiguration c ist im allgemeinen nicht regulär. Äquivalenz als Relation über dem Monoid der Zustands- und Kellerzeichen ist im allgemeinen keine rationale Transduction.