Der Satz von Myhill-Nerode und Minimalautomaten (Theoretische Informatik)

Über die sogenannte Nerode-Relation erhält man ein notwendiges und hinreichendes Kriterium dafür, dass eine Sprache regulär ist. Und mithilfe dieser Äquivalenzrelation kann man auch Automaten mit einer minimalen Anzahl von Zuständen konstruieren.

* Das GANZ NEUE Buch: http://weitz.de/GDM/
* Das NEUE Buch: http://weitz.de/PP/
* Skript: http://weitz.de/files/ti-skript.pdf

* Äquivalenzrelationen:    • Was sind Äquivalenzrelationen?  

* Das Video im Playlist-Kontext: http://weitz.de/y/RcDjuXLK-Jg?list=PL...

* Liste aller Videos: http://weitz.de/haw-videos/
* Das etwas andere Mathe-Lehrbuch: http://weitz.de/KMFI/
* "FAQ": http://weitz.de/youtube.html

00:00 Die Nerode-Relation
12:42 Der Satz von Myhill-Nerode
17:21 Konstruktion eines Automaten aus Äquivalenzklassen
21:38 Der Minimalautomat für eine Sprache
26:20 Konvertierung eines Automaten in den Minimalautomaten