Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
faecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:start [01.06.2022 18:02] – [Definition Grammatik einer formalen Sprache] sbel | faecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Formale Sprachen - Einführung ====== | ||
- | |||
- | Eine natürliche Sprache wie Deutsche, Englisch oder gar Chinesisch hat äußerst komplexe Regeln, die über Jahrhunderte gewachsen sind. Ob ein Satz in einer Sprache korrekt ist, entscheidet ein geübter Sprecher der Sprache meist intuitiv. | ||
- | |||
- | Jemand, der die Sprache erst lernt, müsste anhand von Regeln ableiten, ob ein Satz der " | ||
- | |||
- | Da natürliche Sprachen viel zu komplexen Regeln folgen, betrachten wir im Folgenden nur " | ||
- | |||
- | <WRAP center round tip 80%> | ||
- | **Frage:** Was ist nötig, um eine künstliche Sprache formal zu definieren? | ||
- | </ | ||
- | |||
- | ===== Hunde, die bellen, rennen (nicht)? ===== | ||
- | |||
- | {{ : | ||
- | |||
- | Wir betrachten eine sehr einfache Sprache, diese besteht aus Subjekten und Objekten. Insgesamt kann man Sätze bilden aus den Bestandteilen '' | ||
- | |||
- | Zwei der Elemente sind Subjekte (Higgs und Emil), zwei sind Prädikate (bellen, rennen), man kann auf genau eine Weise einen Satz bilden: | ||
- | |||
- | < | ||
- | |||
- | |||
- | ---- | ||
- | {{: | ||
- | === (A1) === | ||
- | Unsere Sprache hat vier verschiedene " | ||
- | |||
- | |||
- | ===== Bestandteile unserer Sprache ===== | ||
- | |||
- | ==== Alphabet ==== | ||
- | |||
- | |||
- | <WRAP center round important 80%> | ||
- | Um eine Sprache formal zu definieren, muss man zunächst ein **Alphabet Σ**((Sigma)) festlegen. Das Alphabet umfasst alle Symbole, aus denen Wörter/ | ||
- | </ | ||
- | |||
- | |||
- | In unserem Beispiel besteht das Alphabet aus den Symbolen " | ||
- | |||
- | **Σ={Higgs, | ||
- | |||
- | Vorsicht Falle: Im normalen Sprachgebrauch bezeichnet ein Alphabet eine Menge aus einzelnen Zeichen. Bei formalen Sprachen kann ein Alphabet auch Zeichenfolgen (= Symbole) enthalten. Die Zeichenfolge " | ||
- | |||
- | Das Alphabet wird häufig auch als die <color # | ||
- | |||
- | ==== Regeln ==== | ||
- | |||
- | Außer dem Alphabet benötigt man eine Menge von Regeln, die festlegen, wie in der Sprache ein gültiger Satz gebildet wird. Man draf also nicht einfach Symbole des Alphabets beliebig aneinanderreihen, | ||
- | |||
- | <WRAP center round important 80%> | ||
- | Die Menge an Regeln, nach der sie Sätze unserer Sprache entstehen, wird mit **P** bezeichnet((P steht für " | ||
- | </ | ||
- | |||
- | |||
- | Aufgeschrieben werden die Regeln zum Beispiel so: | ||
- | |||
- | S -> H T | ||
- | |||
- | S, H und T sind dabei " | ||
- | |||
- | In unserem Beispiel kann man jetzt die folgenden Regelmenge **P** festlegen: | ||
- | |||
- | S -> H T // Start, dann etwas, das im Platzhalter H steht, dann etwas das im Platzhalter T steht | ||
- | H -> Higgs // Im Platzehalter H kann Higgs stehen | ||
- | H -> Emil // Im Platzhalter H kann Emil stehen | ||
- | T -> bellt // Im Platzhalter T kann bellen stehen | ||
- | T -> rennt // Im Platzhalter T kann rennen stehen | ||
- | | ||
- | Dabei haben wir die **Variablenmenge V** verwendet: **V={S, | ||
- | |||
- | Da es - wie in diesem Beispiel - häufig vorkommt, dass eine Variable alternativ für mehrere unterschiedliche Ersetzungen stehen kann, kürzt man das häufig folgendermaßen ab: | ||
- | |||
- | S -> H T // Start, ein Element aus H dann ein Element aus T | ||
- | H -> Higgs | Emil // In H kann Higgs oder Emil stehen (der senkrechte Strich steht also für " | ||
- | T -> bellt | rennt // In T kann bellen oder rennen stehen | ||
- | |||
- | |||
- | ---- | ||
- | {{: | ||
- | === (A2) === | ||
- | |||
- | * Mache dir klar, dass du unter Verwendung von Alphabet Σ, Produktionen P und Variablen V alle vier Sätze unserer Sprache bilden kannst, wenn du weißt, wo deine Regeln beginnen (S). | ||
- | * Entwerfe einen endlichen Automaten, der nur korrekte Sätze der Sprache akzeptiert. | ||
- | * Was muss du alles anpassen, damit die Hunde auch beide fressen können? | ||
- | ==== Definition Grammatik einer formalen Sprache ==== | ||
- | |||
- | <WRAP center round important 80%> | ||
- | |||
- | Die Einzelteile | ||
- | |||
- | V: Variablenmenge (Menge der Nichtterminale) | ||
- | Σ: Alphabet (Menge der Terminale) | ||
- | P: Produktionen (Ersetzungsregeln) | ||
- | S: Startvariable | ||
- | |||
- | Bilden zusammen eine **Grammatik** **G**, welche die Sprache **L** beschreibt. man schreibt kurz: | ||
- | |||
- | G=(V, | ||
- | | ||
- | </ | ||
- | |||
- | Die Sprache **L** ist die Menge aller **Wörter**, | ||
- | |||
- | **Achtung: | ||
- | |||
- | **Ableiten** bedeutet im Zusammenhang der formalen Sprachen, dass die linke Seite einer Regel durch die entsprechende rechte Seite ersetzt wird. | ||
- | |||
- | ---- | ||
- | {{: | ||
- | === (A3) === | ||
- | |||
- | Die Mengen | ||
- | |||
- | Σ = { der, die, das, Hund, Katze, jagt, kleine, bissige, große } | ||
- | V = { < | ||
- | // < | ||
- | P = { | ||
- | < | ||
- | < | ||
- | < | ||
- | < | ||
- | < | ||
- | < | ||
- | < | ||
- | < | ||
- | } | ||
- | |||
- | Leite 5 gültige Worte der Sprache L ab, die durch die Grammatik '' | ||
- | |||
- | ==== Ein leeres Symbol ==== | ||
- | |||
- | Zusätzlich zu Variablen und Alphabetsymbolen kann auf der rechten Seite einer Regel das "leere Wort" ε((Epsilon, | ||
- | |||
- | ---- | ||
- | {{: | ||
- | === (A4) === | ||
- | |||
- | Gegeben ist | ||
- | Σ = {a, b} | ||
- | V = { S } | ||
- | P = { S -> aSb | ε } | ||
- | |||
- | |||
- | Welche Worte hat die Sprache, die durch G=(V, | ||
- | |||
- | ===== Material ===== | ||
- | |||
- | {{simplefilelist>: |