Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste ÜberarbeitungBeide Seiten der Revision | ||
faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [29.09.2020 15:19] – [Autokennzeichen] sbel | faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [13.10.2020 15:28] – [Autokennzeichen] sbel | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Übungen: Formale Sprachen ====== | ====== Übungen: Formale Sprachen ====== | ||
+ | |||
+ | Grundsätzlich: | ||
+ | |||
+ | ===== PGM Bilder ===== | ||
+ | |||
+ | |||
+ | PGM (Portable Graymap) kann als Sprache zur Beschreibung von Graustufenbildern aufgefasst werden. Das folgende Bild | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | wird wie folgt in der Sprache PGM beschrieben: | ||
+ | |||
+ | < | ||
+ | P2 4 3 7 0 1 2 3 4 5 6 7 6 0 3 0 1 0 5 1 2 | ||
+ | </ | ||
+ | |||
+ | * 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)) | ||
+ | |||
+ | < | ||
+ | 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 | ||
+ | </ | ||
+ | * 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: | + | Beispiel: |
* 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? | ||
===== 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 | ||
+ | |||
+ | Finde eine Ableitung für das Wort '' |