Benutzer-Werkzeuge
se:automatentheorie
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:automatentheorie [2008-12-01 16:40] stefan |
se:automatentheorie [2008-12-01 16:55] stefan |
||
|---|---|---|---|
| Zeile 100: | Zeile 100: | ||
| * P: Menge der Produktionen (Ersetzungsregeln) | * P: Menge der Produktionen (Ersetzungsregeln) | ||
| * eine durch G erzeugte Sprache: L(G) = { x ∈ T<sup>*</sup> | S ⇒<sup>*</sup> x} (alle Wörter, die aus dem Startsymbol abgeleitet werden können) | * eine durch G erzeugte Sprache: L(G) = { x ∈ T<sup>*</sup> | S ⇒<sup>*</sup> x} (alle Wörter, die aus dem Startsymbol abgeleitet werden können) | ||
| - | * Chomsky-Hierarchie (Typ(i + 1) ist gleichzeitig vom Typ(i)) | + | * Chomsky-Hierarchie (Typ(i + 1) ist gleichzeitig vom Typ(i)) definiert 4 Typen von Grammatiken |
| * Typ 0 (allgemeine Grammatiken): keine Einschränkung der Produktionen | * Typ 0 (allgemeine Grammatiken): keine Einschränkung der Produktionen | ||
| * Beispiele: aBc → B, B → c, bA → B, B → aaa | * Beispiele: aBc → B, B → c, bA → B, B → aaa | ||
| Zeile 121: | Zeile 121: | ||
| * Sei L eine formale Sprache. L ist regulär, wenn es eine lineare Grammatik G gibt mit L = L(G) (Grammatiken vom Typ 3 erzeugen reguläre Sprachen) | * Sei L eine formale Sprache. L ist regulär, wenn es eine lineare Grammatik G gibt mit L = L(G) (Grammatiken vom Typ 3 erzeugen reguläre Sprachen) | ||
| * Um eine Grammatik vom Typ 3 durch einen Automaten abzubilden, müssen Regeln der Form A → t ersetzt werden durch A → tN<sub>ε</sub> und N<sub>ε</sub> → ε | * Um eine Grammatik vom Typ 3 durch einen Automaten abzubilden, müssen Regeln der Form A → t ersetzt werden durch A → tN<sub>ε</sub> und N<sub>ε</sub> → ε | ||
| + | * Für jede Transition in einen Endzustand müssen zwei Produktionen vorhanden sein, wenn im Endzustand weitere Eingaben erlaubt (aber nicht verpflichtend) sind: (Beispielautomat "otto" erkennen, Endzustand W) V → o | oW, W → o | t | oW | tW | ||
| + | * Typische Fragen zu Grammatiken | ||
| + | * Typ nach Chomsky? -> Produktionen untersuchen | ||
| + | * Ist G in Normalform? -> Produktionen untersuchen, Verstöße gegen Normalform suchen | ||
| + | * Ist die Ableitung des Wortes xyz möglich? -> mit den Produktionen ausgehend von S versuchen, das Wort nachzubauen | ||
| ==== Überführung einer Grammatik in Normalform ==== | ==== Überführung einer Grammatik in Normalform ==== | ||
| Zeile 126: | Zeile 131: | ||
| * A → aaB ersetzen durch A → aC, C → aB | * A → aaB ersetzen durch A → aC, C → aB | ||
| * A → B ersetzen durch A → w | B ⇒<sup>*</sup> w | * A → B ersetzen durch A → w | B ⇒<sup>*</sup> w | ||
| - | * Für jede Transition in einen Endzustand müssen zwei Produktionen vorhanden sein! | ||
| * alle Regeln sind nun von der Form A → a oder A → aB | * alle Regeln sind nun von der Form A → a oder A → aB | ||
| * Typ 2 | * Typ 2 | ||
| Zeile 137: | Zeile 141: | ||
| * Übung: NEA in DEA überführen | * Übung: NEA in DEA überführen | ||
| * Skript Herold lesen | * Skript Herold lesen | ||
| - | * Definition reguläre Sprache | ||
| - | * Normalformen | ||
| * Kann man Automaten mit LaTeX setzen? | * Kann man Automaten mit LaTeX setzen? | ||
| * Beispiele aus Vorlesung nochmal machen | * Beispiele aus Vorlesung nochmal machen | ||
| * Aufgaben 3.5.2 machen | * Aufgaben 3.5.2 machen | ||
se/automatentheorie.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
