Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | |||
faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [13.10.2020 15:29] – sbel | faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== Ü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 ===== | ||
- | |||
- | 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: 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? | ||
- | |||
- | ===== Ganze Zahlen ===== | ||
- | |||
- | Stellen Sie eine Grammatik auf, um eine Sprache zu erzeugen, die alle ganzen Zahlen enthält. Dabei dürfen keine führenden Nullen vorkommen, die Zahl 00123 ist z.B. verboten. | ||
- | |||
- | ===== Palindrome ===== | ||
- | |||
- | Als Palindrom bezeichnet man Zahlen, Wörter oder Sätze, die von vorne und hinten gleich gelesen werden können. | ||
- | Beispiele: 12321, " | ||
- | |||
- | * Gib eine Grammatik für Palindromzahlen an, die eine ungerade Anzahl an Ziffern haben. | ||
- | * Lasse auch gerade Anzahlen von Ziffern zu und gib eine Ableitung von " | ||
- | |||
- | ===== Seltsame Sprache ===== | ||
- | |||
- | Die Ureinwohner einer bislang unerforschten Insel reden eine seltsame Sprache, die nur aus den Lauten " | ||
- | |||
- | <S> → Da | Li | ||
- | <S> → DaDa< | ||
- | <L> → Li | < | ||
- | |||
- | Gehören die folgenden Wörter zur Sprache der Inselbewohner? | ||
- | |||
- | a) DaDaLiMo | ||
- | b) LiDaMoMo | ||
- | c) LiMo | ||
- | d) DaLiLiMo | ||
- | e) DaDaDaDaLi | ||
- | f) DaDaDaLiLi | ||
- | g) DaLiDaDaMo | ||
- | h) DaMoLiMo | ||
- | |||
- | ===== Mathematische Terme ===== | ||
- | |||
- | (schwer) | ||
- | |||
- | Gib die Grammatik einer formalen Sprache an, die korrekte Rechenterme darstellt. | ||
- | |||
- | Als Alphabet Σ sollen die Symbole '' | ||
- | |||
- | Finde eine Ableitung für das Wort '' |