faecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:start [01.06.2022 16:02] – [Definition Grammatik einer formalen Sprache] sbelfaecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:start [26.02.2025 08:06] (aktuell) – [Definition Grammatik einer formalen Sprache] Marco Kuemmel
Zeile 2: Zeile 2:
  
  
-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.+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.  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 Autiomaten (den Compilern) verarbeitet werden.+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.
  
 <WRAP center round tip 80%> <WRAP center round tip 80%>
Zeile 16: Zeile 16:
 {{ :faecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:higgs_emil.jpg?400 |}} {{ :faecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:higgs_emil.jpg?400 |}}
  
-Wir betrachten eine sehr einfache Sprache, diese besteht aus Subjekten und Objekten. Insgesamt kann man Sätze bilden aus den Bestandteilen ''{Higgs, Emil, bellen, rennen}''. +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:  Zwei der Elemente sind Subjekte (Higgs und Emil), zwei sind Prädikate (bellen, rennen), man kann auf genau eine Weise einen Satz bilden: 
Zeile 39: Zeile 39:
  
  
-In unserem Beispiel besteht das Alphabet aus den Symbolen "Higgs", "Emil", "bellen" und "rennen". Man schreibt kurz:+In unserem Beispiel besteht das Alphabet aus den Symbolen "Higgs", "Emil", "bellt" und "rennt". Man schreibt kurz:
  
-**Σ={Higgs, Emil, bellen, rennen}**+**Σ={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. 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.
Zeile 49: Zeile 49:
 ==== Regeln ==== ==== 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, um gültige Sätze zu bekommen, sondern man muss diese Regeln beachten.+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.
  
 <WRAP center round important 80%> <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 "productions" oder "Produktionen")).+Die Menge an Regeln, nach der die Sätze unserer Sprache entstehen, wird mit **P** bezeichnet((P steht für "productions" oder "Produktionen")).
 </WRAP> </WRAP>
  
Zeile 67: Zeile 67:
   H -> Higgs     // Im Platzehalter H kann Higgs stehen   H -> Higgs     // Im Platzehalter H kann Higgs stehen
   H -> Emil      // Im Platzhalter H kann Emil stehen   H -> Emil      // Im Platzhalter H kann Emil stehen
-  T -> bellt     // Im Platzhalter T kann bellen stehen +  T -> bellt     // Im Platzhalter T kann bellt stehen 
-  T -> rennt     // Im Platzhalter T kann rennen 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 <color #22b14c>Nichtterminale</color>, sie anders als die Terminale des Alphabets, bei der Bildung von Worten der Sprache solange ersetzt werden, bis sie "verschwinden".+Dabei haben wir die **Variablenmenge V** verwendet: **V={S,H,T}**, wobei S die besondere Rolle der Startvariablen zukommt. Die Variablen heißen auch <color #22b14c>Nichtterminale</color>, 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: 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:
Zeile 76: Zeile 76:
   S -> H T             // Start, ein Element aus H dann ein Element aus T    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")   H -> Higgs | Emil    // In H kann Higgs oder Emil stehen (der senkrechte Strich steht also für "oder")
-  T -> bellt | rennt   // In T kann bellen oder rennen stehen+  T -> bellt | rennt   // In T kann bellt oder rennt stehen
    
  
Zeile 86: Zeile 86:
   * Entwerfe einen endlichen Automaten, der nur korrekte Sätze der Sprache akzeptiert.   * 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?   * Was muss du alles anpassen, damit die Hunde auch beide fressen können?
 +
 +
 ==== Definition Grammatik einer formalen Sprache ==== ==== Definition Grammatik einer formalen Sprache ====
  
 <WRAP center round important 80%> <WRAP center round important 80%>
  
-Die Einzelteile+Die Einzelteile (das 4-Tupel)
  
    V: Variablenmenge (Menge der Nichtterminale)    V: Variablenmenge (Menge der Nichtterminale)
Zeile 97: Zeile 99:
    S: Startvariable    S: Startvariable
  
-Bilden zusammen eine **Grammatik** **G**, welche die Sprache **L** beschreibt. man schreibt kurz:+bilden zusammen eine **Grammatik** **G**, welche die Sprache **L** beschreibt. Man schreibt kurz:
  
   G=(V,Σ,P,S)   G=(V,Σ,P,S)
      
 </WRAP> </WRAP>
-  
-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...+==== Wichtige Begrifflichkeiten ==== 
 + 
 +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. \\ 
 +Wichtig: Obwohl man "Higgs rennt" im normalen Sprachgebrauch als Satz bezeichnen würde, ist das im Sinne der formalen Sprachen ein Wort - das war oben die ganze Zeit so, wir haben also die ganze Zeit "Worte" unserer Sprache gebildet, keine Sätze.
  
 **Ableiten** bedeutet im Zusammenhang der formalen Sprachen, dass die linke Seite einer Regel durch die entsprechende rechte Seite ersetzt wird. **Ableiten** bedeutet im Zusammenhang der formalen Sprachen, dass die linke Seite einer Regel durch die entsprechende rechte Seite ersetzt wird.
 +
 +Die **Syntax** einer Sprache beschreibt die Regeln, nach denen die Sprachkonstrukte gebildet werden. 
 +
 +Die **Semantik** einer Sprache beschreibt die Bedeutung der Sprachkonstrukte. 
 +
 +Die **Pragmatik** einer Sprache beschäftigt sich mit der Verwendung und Bedeutung von Sprachkonstrukten in konkreten Situationen. 
  
 ----        ----       
Zeile 130: Zeile 139:
  
 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. 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.
 +
 +
 +==== Syntaxdiagramm ====
 +
 +Man kann eine Grammatik auch als **<color #22b14c>Syntaxdiagramm</color>** darstellen. Für unsere Hundesprache würde das so aussehen:
 +
 +{{ :faecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:hundesprache.png |}}
 +
 +
 +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 **<color #22b14c>Railroad-Diagramm</color>**.
 +
 +
 +Mit dem Tool [[https://rr.red-dove.com/|"RR - Railroad Diagram Generator"]]((Source: https://github.com/GuntherRademacher/rr)) 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''
 +
 +----       
 +{{:aufgabe.png?nolink  |}}
 +=== (A4) ===
 +Überführe die Grammatik aus Aufgabe 3 mit RR in ein Syntaxdiagramm 
 +
 +++++ Lösung |
 +
 +<code>
 +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' 
 +</code> 
 +
 +++++
 +
 +Wie kann man aus dem Syntaxdiagramm die Bestandteile der Grammatik ermitteln? Beschreibe das Vorgehen.
  
 ==== Ein leeres Symbol ==== ==== Ein leeres Symbol ====
Zeile 137: Zeile 189:
 ----        ----       
 {{:aufgabe.png?nolink  |}} {{:aufgabe.png?nolink  |}}
-=== (A4) ===+=== (A5) ===
  
 Gegeben ist  Gegeben ist 
  • faecher/informatik/oberstufe/automaten/formale_sprachen/einfuehrung/start.1654099339.txt.gz
  • Zuletzt geändert: 01.06.2022 16:02
  • von sbel