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 [14.12.2023 10:29] – [Formale Sprachen - Einführung] Svenja Müllerfaecher:informatik:oberstufe:automaten:formale_sprachen:einfuehrung:start [26.02.2025 08:06] (aktuell) – [Definition Grammatik einer formalen Sprache] Marco Kuemmel
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 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 70: Zeile 70:
   T -> rennt     // Im Platzhalter T kann rennt 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 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 ====
  
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 146: Zeile 155:
  
  
-Mit dem Tool [[https://www.bottlecaps.de/rr/ui|"Bottlecaps"]] kann man eine Grammatik eingeben und erhält dann ein Syntaxdiagramm. Dabei gelten folgende Konventionen:+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 Bottlecaps als ''::='' geschrieben. Aus ''A->B'' wird also ''A::=B''. +  * Der Ersetzungspfeil ''->'' wird in RR als ''::='' geschrieben. Aus ''A->B'' wird also ''A::=B''. 
-  * Terminalsymbole werden in einfachen Hochhkommas geschrieben. Aus ''A-> B k'' wird ''A::=B 'k' ''+  * 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''   * Alternativen werden wie in unserer Schreibweise durch einen senkrechten Strich dargestellt: ''A-> B|C'' wird ''A::=B|C''
  
Zeile 155: Zeile 164:
 {{:aufgabe.png?nolink  |}} {{:aufgabe.png?nolink  |}}
 === (A4) === === (A4) ===
-Überführe die Grammatik aus Aufgabe 3 mit Bottlecaps in ein Syntaxdiagramm +Überführe die Grammatik aus Aufgabe 3 mit RR in ein Syntaxdiagramm 
  
 ++++ Lösung | ++++ Lösung |
  • faecher/informatik/oberstufe/automaten/formale_sprachen/einfuehrung/start.1702549773.txt.gz
  • Zuletzt geändert: 14.12.2023 10:29
  • von Svenja Müller