faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung		 Vorhergehende Überarbeitung
Letzte ÜberarbeitungBeide Seiten der Revision
faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [29.09.2020 15:19] – [Autokennzeichen] sbelfaecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [13.10.2020 15:29] – sbel
Zeile 1: Zeile 1:
 ====== Übungen: Formale Sprachen ====== ====== Übungen: Formale Sprachen ======
  
 +
 +Grundsätzlich: Um eine Grammatik zu finden, überlegt man sich, wie die **Bestandteile** der Grammatik beschaffen sein müssen. Was ist das Eingabealphabet, was für Variablen benötige ich, wie sehen die Produktionen aus. Dabei ist es natürlich denkbar, dass man bei den Überlegungen feststellt, dass man weitere Variablen benötigt oder die Regeln anpassen muss.
 +
 +===== PGM Bilder =====
 + 
 +
 +PGM (Portable Graymap) kann als Sprache zur Beschreibung von Graustufenbildern aufgefasst werden. Das folgende Bild
 +
 +{{ :faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:auswahl_182.png |}}
 +
 +wird wie folgt in der Sprache PGM beschrieben:
 +
 +<code>
 +P2 4 3 7 0 1 2 3 4 5 6 7 6 0 3 0 1 0 5 1 2
 +</code>
 +
 +  * Welches Alphabet Σ liegt der Sprache PGM zu Grunde? Gib Beispiele für Wörter über Σ an, die zu PGM bzw. nicht zu PGM gehören.
 +  * Ist der folgende Ausdruck ein Wort der der Sprache PGM? wenn ja - was stellt das folgende PGM Bild dar?((Tipp: Man darf beliebig Zeilenumbrüche einfügen, ohne das Format zu zerstören))
 +
 +<code>
 +P2 24 7 15 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0  3  3  3  3  0  0  7  7  7  7  0  0 11 11 11 11  0  0 15 15 15 15  0 0  3  0  0  0  0  0  7  0  0  0  0  0 11  0  0  0  0  0 15  0  0 15  0 0  3  3  3  0  0  0  7  7  7  0  0  0 11 11 11  0  0  0 15 15 15 15  0 0  3  0  0  0  0  0  7  0  0  0  0  0 11  0  0  0  0  0 15  0  0  0  0 0  3  0  0  0  0  0  7  7  7  7  0  0 11 11 11 11  0  0 15  0  0  0  0 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
 +</code>
 +  * Wie sieht ein ein endlicher Automat aus, der die Gültigkeit von 3x3 PNG Bilder mit 9 Graustufen überprüfen kann?
 +
 + 
  
 ===== Autokennzeichen ===== ===== Autokennzeichen =====
Zeile 6: Zeile 31:
 Deutsche Autokennzeichen sind nach dem Prinzip aufgebaut, dass sie mit dem Ortskennzeichen (ein bis drei Buchstaben, Umlaute eingeschlossen) beginnen, es folgen ein oder zwei Buchstaben (ohne Umlaute) sowie 1 bis 4 Zahlen. Die drei Teile werden von Bindestrichen getrennt. Deutsche Autokennzeichen sind nach dem Prinzip aufgebaut, dass sie mit dem Ortskennzeichen (ein bis drei Buchstaben, Umlaute eingeschlossen) beginnen, es folgen ein oder zwei Buchstaben (ohne Umlaute) sowie 1 bis 4 Zahlen. Die drei Teile werden von Bindestrichen getrennt.
  
-Beispiel: TÜ-IT-1337+Beispiel: B-IN-42
  
   *  Formuliere eine Grammatik, bestehend aus dem Alphabet Σ, der Variablenmenge V, der Startvariablen S und der Menge von Produktionsregeln P.    *  Formuliere eine Grammatik, bestehend aus dem Alphabet Σ, der Variablenmenge V, der Startvariablen S und der Menge von Produktionsregeln P. 
   * Leite das Wort der Grammatik TÜ-IT-1337 anhand der formulierten Regeln ab.    * Leite das Wort der Grammatik TÜ-IT-1337 anhand der formulierten Regeln ab. 
 +  * Kannst du ein Railroad Diagramm erzeugen?(([[https://bottlecaps.de/rr/ui|Bottlecaps]]))
  
 ===== Ganze Zahlen ===== ===== Ganze Zahlen =====
Zeile 42: Zeile 68:
     h) DaMoLiMo     h) DaMoLiMo
  
-Mathematische Terme +===== Mathematische Terme ===== 
-Geben Sie die Grammatik einer formalen Sprache an, die korrekte Rechenterme darstellt. Als Alphabet Σ sollen die Symbole { (, ), +, -, *, /, 0, 1, 2, ..., 9 } verwendet werden. Es soll eine beliebige Klammerungstiefe möglich sein. + 
-Finden Sie eine Ableitung für das Wort (40 – (2 * 14)) / 6 der Sprache.+(schwer) 
 + 
 +Gib die Grammatik einer formalen Sprache an, die korrekte Rechenterme darstellt.  
 + 
 +Als Alphabet Σ sollen die Symbole ''{ (, ), +, -, *, /, 0, 1, 2, ..., 9 }'' verwendet werden. Es soll eine beliebige Klammerungstiefe möglich sein. 
 + 
 +Finde eine Ableitung für das Wort ''(40 – (2 * 14)) / 6'' der Sprache.