Übungen: Formale Sprachen

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.

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

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.