Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [29.09.2020 13:19] – [Autokennzeichen] sbel
+++ faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [24.01.2025 15:12] (aktuell) – [Palindrome] Marco Kuemmel
@@ Zeile 1: / Zeile 1: @@
 ====== Ü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 =====
@@ 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.
-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.
   * Leite das Wort der Grammatik TÜ-IT-1337 anhand der formulierten Regeln ab.
+  * Kannst du ein Railroad Diagramm erzeugen?(([[https://rr.red-dove.com/|RR]]))
 ===== Ganze Zahlen =====
@@ Zeile 20: / Zeile 46: @@
 Beispiele: 12321, "Rentner", "Trug Tim eine so helle Hose nie mit Gurt?"
-  * Gib eine Grammatik für Palindromzahlen an, die eine ungerade Anzahl an Ziffern haben.
+  * Gib eine Grammatik für Palindrom**zahlen** an, die eine ungerade Anzahl an Ziffern haben.
   * Lasse auch gerade Anzahlen von Ziffern zu und gib eine Ableitung von "123321" an.
@@ Zeile 42: / Zeile 68: @@
     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.