Prof. Dr. Franz Schweiggert -- Sektion Angewandte Informationsverarbeitung -- 17. November 1998
Dr. Andreas Borchert Blatt 5
Ingo Melzer  

[c]



Allgemeine Informatik I (WS 1998/99)


Abgabetermin 25. November 1998

4 Automatisch (10 Punkte)

Für die folgenden Aufgaben sei immer das Alphabet $\Sigma = \{a,b,c\}$.Die Nichterminalsymbole seien $N=\{S,A,B,C\}$, wobei S das Startsymbol sei. Bestimmen Sie Lösungen zu folgenden Aufgaben:

• Leiten Sie das Wort aaabbabbba mit Hilfe von folgenden Produktionen P ab:
  $S\to aBbA, A\to a\vert aS\vert bAA, B\to b\vert bS\vert aBB$
• Ein Palindrom ist ein Wort, das von rechts und von links gelesen identisch ist (also identisch zu seinem ,,Spiegelbild``). Geben Sie Produktionen P an, mit denen sich genau alle Palindrome über obigem Alphabet ableiten lassen.
• Geben Sie einen Automaten und einen regulären Ausdruck für alle Worte mit einer geraden Anzahl von a's an.
• Geben Sie einen regulären Ausdruck für egrep an, der alle Zeilen findet, die nur aus obigem Alphabet (also $\Sigma^*$) bestehen.