Was versteht man unter einer formalen Sprache?
Eine formale Srache ist eine Menge von Wörtern, die aus einem endlichen Alphabet gebildet werden.
Die endliche Liste kann Zeichen wie Buchstaben oder Zahlen enthalten.
Wann ist ein DEA unvollständig? Wie kann das behoben werden?
Ein deterministischer endlicher Automat ist unvollständig, wenn es keine definierten Übergänge gibt. Heißt, es gibt Zustände, für die der Automat keine Regelung hat und nicht mehr zu händeln weiß.
Beheben lässt es sich durch:
Fehlerzustand hinzufügen: Eine zusätzlichen Fehlerzustand hinzufügen. Akzeptiert alle Eingaben, indem er zu sich selbst übergeht.
Fehlerzustand konfigurieren: Alle fehlenden Übergänge sollen nun auf den Fehlerzustand zeigen.
Übergangsfunktion aktualisieren: Es sollen alle undefinierte Übergänge zum Fehlerzustand führen
Sind reguläre Sprache unter Komplement abgeschlossen?
Ja,
Endzustände in Nicht-Endzustände umwandeln: Alle Zustände, die im ursprünglichen DEA Endzustände waren, werden zu Nicht-Endzuständen.
Nicht-Endzustände in Endzustände umwandeln: Alle Zustände, die im ursprünglichen DEA keine Endzustände waren, werden zu Endzuständen.
Beschreiben Sie, wie Sie generell aus einem NEA einen DEA konstruieren können.
Mit der Subset-Konstruktion
Woraus ergibt sich die Konstante n des Pumping-Lemmas für reguläre Sprache?
Die Konstante n im Pumping-Lemma für reguläre Sprachen ist eine Zahl, die von der Anzahl der Zustände eines DEA abhängt, der die Sprache akzeptiert. Genauer gesagt, n ist mindestens so groß wie die Anzahl der Zustände im DEA.
Bewerten Sie folgende Aussage:
Das Pumping-Lemma für reguläre Sprachen besagt, dass wenn es eine Konstante n gibt, sodass für alle Wörter aus einer Sprache mit Wortlänge größer oder gleich n eine Zerlegung mit w=xyz existiert (mit den 3 Eigenschaften des Lemmas), dann ist die Sprache regulär.
Pumping-Lemma könnte die Sprache auf nicht Regulär prüfen aber nicht ob sie Regulär ist.
Ein endlicher Automat kann nur endliche Sprachen akzeptieren
Die Aussage ist falsch, da endliche Automaten unendliche Sprachen akzeptieren können.
Die Eigenschaft, dass die Konkatenation von zwei Wörtern, die in einer regulären Sprache L sind, immer in L liegt, gilt nur für Sprachen, die so strukturiert sind, dass sie alle möglichen Konkatenationen ihrer Wörter enthalten. Im Allgemeinen kann man das nicht von der Regulärität der Sprache L allein ableiten.
Last changeda month ago