Formale Sprachen - Einführung

Eine natürliche Sprache wie Deutsch, 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 "Grammatik" der Sprache entspricht, also ob der Satz in der Sprache akzeptiert wird.

Da natürliche Sprachen viel zu komplexen Regeln folgen, betrachten wir im Folgenden nur "künstliche" Sprachen, was im Zusammenhang der Informatik auch deswegen Sinn macht, da es sich bei den meisten "Programmiersprachen" um künstliche Sprachen handelt, die von Automaten (den Compilern) verarbeitet werden.

Wir betrachten eine sehr einfache Sprache, diese besteht aus Subjekten und Objekten. Insgesamt kann man Sätze bilden aus den Bestandteilen {Higgs, Emil, bellt, rennt}.

Zwei der Elemente sind Subjekte (Higgs und Emil), zwei sind Prädikate (bellen, rennen), man kann auf genau eine Weise einen Satz bilden:

<Subjekt> <Prädikat>

Unsere Sprache hat vier verschiedene "Sätze" - welche?

In unserem Beispiel besteht das Alphabet aus den Symbolen "Higgs", "Emil", "bellt" und "rennt". Man schreibt kurz:

Σ={Higgs, Emil, bellt, rennt}

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 "Higgs" ist also ein Symbol unseres Alphabets.

Das Alphabet wird häufig auch als die Menge der Terminale bezeichnet.

Außer dem Alphabet benötigt man eine Menge von Regeln, die festlegen, wie in der Sprache ein gültiger Satz gebildet wird. Man darf also nicht einfach Symbole des Alphabets beliebig aneinanderreihen, um gültige Sätze zu bekommen, sondern man muss diese Regeln beachten.

Aufgeschrieben werden die Regeln zum Beispiel so:

S -> H T

S, H und T sind dabei "syntaktische Variablen", also Platzhalter für Symbole des Alphabets³⁾. S hat eine besondere Rolle, und bezeichnet die Startvariable, also diejenige Regeln, an der die Satzbildung beginnt.

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 bellt stehen
T -> rennt     // Im Platzhalter T kann rennt stehen

Dabei haben wir die Variablenmenge V verwendet: V={S,H,T}, wobei S die besondere Rolle der Startvariablen zukommt. Die Variablen heißen auch Nichtterminale, die anders als die Terminale des Alphabets, bei der Bildung von Worten der Sprache solange ersetzt werden, bis sie "verschwinden".

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 "oder")
T -> bellt | rennt   // In T kann bellt oder rennt stehen

• 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?

 V: Variablenmenge (Menge der Nichtterminale)
 Σ: Alphabet (Menge der Terminale)
 P: Produktionen (Ersetzungsregeln)
 S: Startvariable

G=(V,Σ,P,S)

Die Sprache L ist die Menge aller Wörter, die von der Startvariablen S aus anhand der Regeln P der Grammatik abgeleitet werden können.

Achtung: Obwohl man "Higgs rennt" im normalen Sprachgebrauch als Satz bezeichnen würde, ist das im Sinne der formalen Sprachen ein Wort - das war oben wie ganze Zeit so, wir haben also die ganze Zeit "Worte" unserer Sprache gebildet, keine Sätze, aber um euch nicht zu verwirren…

Ableiten bedeutet im Zusammenhang der formalen Sprachen, dass die linke Seite einer Regel durch die entsprechende rechte Seite ersetzt wird.

Die Mengen

Σ = { der, die, das, Hund, Katze, jagt, kleine, bissige, große }
V = { <Satz>, <Subjekt>, <Prädikat>, <Objekt>, <Artikel>, <Attribut>, <Adjektiv>, <Substantiv> } 
    // <Satz> ist Startvariable
P = { 
    <Satz>       ->   <Subjekt> <Prädikat> <Objekt>, 
    <Subjekt>    ->   <Artikel> <Attribut> <Substantiv>, 
    <Objekt>     ->   <Artikel> <Attribut> <Substantiv>,
    <Artikel>    ->   der | die | das, 
    <Attribut>   ->   <Adjektiv> | <Adjektiv> <Attribut>,
    <Adjektiv>   ->   kleine | bissige | große,
    <Substantiv> ->   Hund | Katze, 
    <Prädikat>   ->   jagt }
    }

Leite 5 gültige Worte der Sprache L ab, die durch die Grammatik G=(V,Σ,P,S) definiert ist und notiere jeweils den gesamten Weg der Ableitung.

Man kann eine Grammatik auch als Syntaxdiagramm darstellen. Für unsere Hundesprache würde das so aussehen:

Die Symbolformen haben dabei die folgende Bedeutung:

• Rechtecke mit scharfen Ecken sind Nichtterminalsymbole (Variablen). Diese müssen also an anderer Stelle durch Terminalsymbole definiert werden.
• Die Rechtecke mit runden Ecken sind Terminalsymbole
• Gültige Wörter der Sprache findet man, indem man wie eine Zug auf den Linien "fährt", Alternativen stellen sich als "Weichen" dar, Nichtterminale werden auf die gleiche Weise ersetzt bis das Wort nur noch aus Terminalsymbolen besteht. Wegen dieses Vorgehens nennt mal solche Syntaxdiagramme oft auch Railroad-Diagramm.

Mit dem Tool "RR - Railroad Diagram Generator"⁴⁾ kann man eine Grammatik eingeben und erhält dann ein Syntaxdiagramm. Dabei gelten folgende Konventionen:

• Der Ersetzungspfeil → wird in RR als ::= geschrieben. Aus A→B wird also A::=B.
• Terminalsymbole werden in einfachen Hochkommas geschrieben. Aus A→ B k wird A::=B 'k'
• Alternativen werden wie in unserer Schreibweise durch einen senkrechten Strich dargestellt: A→ B|C wird A::=B|C

Überführe die Grammatik aus Aufgabe 3 mit RR in ein Syntaxdiagramm

Lösung

Satz ::=   Subjekt Prädikat Objekt
Subjekt  ::= Artikel Attribut Substantiv 
Objekt     ::=   Artikel Attribut Substantiv
Artikel    ::=   'der' | 'die' | 'das' 
Attribut   ::=   Adjektiv | Adjektiv Attribut
Adjektiv   ::=   'kleine' | 'bissige' | 'große'
Substantiv ::=   'Hund' | 'Katze' 
Prädikat   ::=   'jagt' 

Wie kann man aus dem Syntaxdiagramm die Bestandteile der Grammatik ermitteln? Beschreibe das Vorgehen.

Zusätzlich zu Variablen und Alphabetsymbolen kann auf der rechten Seite einer Regel das "leere Wort" ε⁵⁾ stehen. Das leere Wort steht für "kein Symbol", manchmal ist seine Verwendung praktisch.

Gegeben ist

Σ = {a, b}
V = { S } 
P = { S -> aSb | ε }

Welche Worte hat die Sprache, die durch G=(V,Σ,P,S) erzeugt wird?⁶⁾