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 [29.09.2020 15:20] – [Seltsame Sprache] 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 ====== | ||
- | |||
- | ===== 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 ===== | ||
- | |||
- | 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 '' |