Formale Sprachen #18 - Nerode-Rechtskongruenz
Vložit
- čas přidán 16. 10. 2014
- Wir führen die Nerode-Rechtskongruenz ein und erhalten so eine Möglichkeit, aus einer Sprache einen DEA zu konstruieren, den kanonischen DEA. Dieser ist minimal und isomorph zum Quotientenautomaten.
Kann es nur 3000 mal wiederholen; Du trägst die Informatikstudenten Deutschlands auf deinen Schultern. Danke!
Sehr gut erklärt. Ohne irgendwelche Versprecher oder Dreher, das ist eine stabile Leistung!
Stabil bruder
Sehr ausführlich und gut verständlich erklärt! Danke dafür! Das Skript meiner Uni besteht gefühlt zu 90 % nur aus Formeln :''''D Das ist auf Dauer sehr anstrengend.
Wir hatten im Skript nur die mathematische Definiton gehabt ohne eine Erklärung. In der Vorlesung hat der Prof die Definition "vorgelesen", ohne es zu erklären. Ich dachte dann "Gut, dann muss es wohl nicht so wichtig sein". Hab mich geirrt. Jetzt hab ich mir dein Video dazu angeschaut und es auf Anhieb verstanden. Danke!
Moin, danke für deine Videos erstmal. EIne Frage hätte ich: An der Stelle 1:43 sagst du, dass wir mit dem Wort "ababa" im dritten Zustand landen, aber das stimmt nach meiner Auffassung nicht, oder übersehe ich da etwas?
Auch in diesem Semester rettest du theoretische Informatik Module!
Vielen Dank🎉
Super erklärt, wie alle Themen, die Du behandelst! Man merkt auch, dass Du einen sehr guten mathematischen Hintergrund hast und daher vieles plausibel herleiten kannst, anstatt es einfach zu postulieren :)
das einzige, was mich ärgert, ist, dass ich die Videos von Dir so spät entdeckt habe! ;)
Danke, es freut mich sehr, dass es hilft! :)
Übrigens wäre ich auch sehr dankbar für Video-Bewertungen (Daumen hoch oder runter), da ich dieses Feedback auswerte und auf lange Sicht auch die am schlechtesten bewerteten Videos überarbeiten und neu aufnehmen möchte.
Danke dir mein Freund. Hoffe du liest die Comments. Schade ,dass du noch nicht so viele Abos hast. Brauchen mehr Leute wie dich, die komplizierte Themen Menschen nah erklären. Weiter so!!!!
Prince Desperado Hey, danke für das Lob! Also mir kommt 2000 Abos schon recht viel vor. :D Aber darfst meinen Kanal auch gerne weiter empfehlen!
Werde ich sehr gerne machen!!!!
Gutes Video.
Danke für die ganzen Videos
hast höchstwahrscheinlich mein Fachgespräch gerettet :b
näheres werd ich morgen wissen^^
Wie ist es gelaufen? Vor 4 Jahren? :D
@@mathiaskrupp691 Wie ist es gelaufen, vor 5 Jahren?
du bist der beste
Top erklärt!
Was ich noch begrüßen würde wäre eine Aufgabe zum Ende jedes Video und die Aufklärung dazu am Ende des nächsten Videos!
Danke, gute Idee!
Hey kann mir jemand damit helfen: Was ist der Nerode Index von dem Ausdruck (10 + 200 + 3000 + 40000)* ? Ich komm darauf dass [1], [2], und [e = leeres Wort] unterschiedliche Äquivalenzklassen sind, aber wenn ich daraus einen Nerode Automaten zu konstruieren versuch, ergibt das keinen Sinn mehr.
Eine sichere Methode, den Index zu finden, wäre die folgende: Konstruiere einen DEA für die Sprache (evtl. erst einen NEA und dann Potenzmengenkonstruktion), minimiere den DEA nach dem Verfahren aus einem der vorigen Videos. Die Anzahl der Zustände ist genau der Nerode-Index.
Ich habe es kurz probiert und habe einen DEA mit 6 Zuständen gefunden, der minimal sein sollte. Die sechs verschiedenen Klassen sind dabei [epsilon], [0], [1], [2], [3], [4].
hey, eine frage, ist die bezeichnung dass eine Sprache erkennbar ist, von gleicher bedeutung dass diese Sprache eine reguläre Sprache (Typ-3 Sprache) ist?
Hey, ja ich hab in dieser Serie immer das Wort "erkennbar" genutzt, aber ich meine damit regulär (Typ 3).
Habe noch nicht ganz verstanden was der Unterschied zwischen dem Quotientenautomat und dem Kanonischen DEA ist. Waere auch interessiert daran, inwiefern sie sich vom Minimal-DEA und dem Myhill-Nerode-Automaten unterscheiden :)
Das Tolle ist: Es gibt keinen Unterschied! All diese Automaten sind genau gleich. Sie sind zwar auf verschiedene Arten definiert, aber: Wenn man mit einem beliebigen DEA beginnt und davon den Quotientenautomaten bildet, dann ist der resultierende DEA minimal. Und er ist auch gleich dem kanonischen DEA, dessen Zustände die Äquivalenzklassen der Nerode-Rechtskongruenz sind.
@@NLogSpace Vielen Dank!
Nerode-Rechtskongruenz 101
Top!
Vielleicht etwas weniger Zeigergewirbel :)