Stück für Stück entpuppt sich Anil Nerodes Rechtskongruenz als der perfekte Test auf Regularität. Wir wussten bereits aus dem vorigen Video, dass reguläre Sprachen bezüglich dieser Relation nur endlich viele Äquivalenzklassen haben. Myhill und Nerode sagen uns, dass die Umkehrung dieser Folgerung ebenfalls gilt. Mehr noch: Wenn wir bei einer Sprache nur endlich viele Äquivalenzklassen vorfinden, dann liefert uns die Rechtskongruenz einen Bauplan für einen Automaten, der die Sprache auch praktisch erkennt. Und minimal ist er auch noch. Was will man mehr!
► Vorlesungsfolien zum Download: iccl.inf.tu-dr... (9. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dr...
► Fehler gefunden? Issues melden auf github: github.com/kno...
Негізгі бет Der Satz von Myhill und Nerode
Пікірлер: 5