Ü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 (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?¹⁾

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?

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?²⁾

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.

Als Palindrom bezeichnet man Zahlen, Wörter oder Sätze, die von vorne und hinten gleich gelesen werden können. 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.
• Lasse auch gerade Anzahlen von Ziffern zu und gib eine Ableitung von "123321" an.

Die Ureinwohner einer bislang unerforschten Insel reden eine seltsame Sprache, die nur aus den Lauten "Da", "Li" und "Mo" besteht. Dabei liegen all ihren Wörtern folgende Ableitungsregeln zugrunde. <S> ist die Startvariable.

<S> → Da | Li
<S> → DaDa<S> | Da<S>Li | <L>Mo
<L> → Li | <L><S>Mo

Gehören die folgenden Wörter zur Sprache der Inselbewohner? Wenn ja, geben Sie eine mögliche Ableitung an.

  a) DaDaLiMo
  b) LiDaMoMo
  c) LiMo
  d) DaLiLiMo
  e) DaDaDaDaLi
  f) DaDaDaLiLi
  g) DaLiDaDaMo
  h) DaMoLiMo

(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.