Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
faecher:informatik:oberstufe:automaten:formale_sprachen:uebungen:start [13.10.2020 15:21] – 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 | ||
- | |||
- | (a) 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. | ||
- | |||
- | (b) Verdeutliche am Beispiel PGM, was man unter Syntax und Semantik einer Sprache versteht. | ||
- | |||
- | ===== 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. | ||
- | |||
- | ===== 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 '' |