Wikipedia · einfach zusammengefasst · Stand
Äquivalenzproblem
Als Äquivalenzproblem bezeichnet man in der Theoretischen Informatik das Problem, zu entscheiden, ob zwei formale Definitionen von zwei Sprachen L 1 …
Inhalt2 Abschnitte
Bedeutung und Entscheidbarkeit
Das Äquivalenzproblem ist ein Problem der Theoretischen Informatik. Es fragt, ob zwei formale Definitionen von Sprachen L₁ und L₂ dieselbe Sprache beschreiben, also ob L₁ = L₂ gilt. Die Sprachen können beispielsweise durch Grammatiken oder Automaten definiert sein.
Für reguläre Grammatiken und deterministisch kontextfreie Grammatiken ist das Problem entscheidbar: Es gibt also ein Verfahren, das stets entscheidet. Für nichtdeterministische kontextfreie Grammatiken ist es unentscheidbar. Wenn ein Äquivalenzproblem entscheidbar ist, ist auch seine Komplexität wichtig; sie kann stark davon abhängen, in welcher Art die Sprachen vorgegeben sind.
Verfahren für reguläre Sprachen
Bei regulären Sprachen ist das Äquivalenzproblem entscheidbar, weil das Leerheitsproblem entscheidbar ist und reguläre Sprachen bestimmte Abschlusseigenschaften besitzen. Es gilt genau dann L₁ = L₂, wenn
(L₁ ∩ L̅₂) ∪ (L₂ ∩ L̅₁) = ∅.
Dabei enthält der Ausdruck alle Wörter, die nur zu einer der beiden Sprachen gehören. Ist diese Menge leer, unterscheiden sich die Sprachen nicht.
Liegen L₁ und L₂ bereits als deterministische endliche Automaten (DEAs) vor, kann man außerdem jeweils den Minimalautomaten bilden und die beiden Minimalautomaten auf Isomorphie prüfen. Sind sie isomorph, sind die Sprachen äquivalent.