Endliche Automaten und Sprachen
HTML-код
- Опубликовано: 1 ноя 2020
- Wie passt die Klasse der "Sprachen endlicher Automaten" eigentlich zur vorher eingeführten Chomsky-Hierarchie? Wir geben die Antwort und beginnen mit der Erklärung der Hintergründe, die uns aber noch über mehrere Videos beschäftigen wird.
► Vorlesungsfolien zum Download: iccl.inf.tu-dresden.de/web/FS... (3. Vorlesung)
► Aktuelle und frühere Versionen der Vorlesung: iccl.inf.tu-dresden.de/web/Fo...
► Fehler gefunden? Issues melden auf github: github.com/knowsys/FormaleSys...
Sie sind zwar nicht mein Professor, aber ich verstehe durch Sie die Sachen sehr gut und besser als durch meinen Professor. Dennoch würde ich Sie gerne fragen, ob solche Beweise auch in Klausuren geführt werden müssen?
1.: Bei 8:18 wie kann die erzeugte Grammatik regulär sein wenn sie nicht kontextfrei mit epsilon Erweiterung ist ? Also q1 ist ja das Startsymbol und bildet auf epsilon ab und kommt trotzdem noch auf einer rechten Seite vor (q4 -> aq1). 2.: Bei 18:39 wird als Abschluss für M mit Epsilon als einzige Möglichkeit angenommen das q0 der Endzustand ist. Allerdings muss das ja nicht so sein, wie in dem davor genutzten Bsp. könnte man auch in q3 mit einem Epsilon Übergang abschließen oder ?
Ja, das ist eine gute Frage. Erstmal zum ersten Teil: "Wie kann die Grammatik regulär sein?" Das liegt ganz einfach daran, dass sie die Eigenschaften erfüllt, die wir für reguläre Grammatiken gefordert hatten. Siehe das Video zur Chomsky-Hierarchie (ruclips.net/video/xJW4d35lihY/видео.html). Regulär ist die Grammatik also. Es stimmt auch, dass die so konstruierte Grammatik nicht unbedingt kontextfrei mit Epsilonerweiterung sein muss.
Der zweite implizite Teil der Frage ist dann: "Muss da nicht irgendwo ein Fehler stecken, wenn eine reguläre Grammatik nicht kontextfrei ist (nicht einmal mit Epsilonerweiterung)?" Die Antwort lautet: Nein, es reicht uns, dass die Sprache durch irgendeine kontextfreie Grammatik mit Epsilonerweiterung dargestellt werden kann. Die Chomsky-Hierarchie besteht aus Familien von Sprachen, nicht aus Familien von Grammatiken. Jede der folgenden Aussagen stimmt also: (1) jede reguläre Sprache ist kontextfrei; (2) jede reguläre Sprache kann durch eine reguläre Grammatik dargestellt werden; (3) jede kontextfreie Sprache kann durch eine kontextfreie Grammatik mit Epsilon dargestellt werden. Trotzdem stimmt die folgende Aussage *nicht*: (4) jede reguläre Grammatik ist kontextfrei mit Epsilonerweiterung. Das sollte uns aber nicht weiter stören.
@@prof.markus6569 Vielen Dank, die Antwort hat viele Fragen beantwortet.