Eine Grammatik \( G \) ist ein 4-Tupel \( G = ( N, T, P, S) \) mit:

• endlicher Menge der Nichtterminale \( N \) (meist Großbuchstaben),
• endlichem Terminalalphabet \( T \) bzw. \( \Sigma \) (meist Kleinbuchstaben oder Ziffern),
• endlicher Menge der Produktionen \( P \) und
• dem Startsymbol \( S \in N \).

Für eine Grammatik gilt zudem \( N \cap T = \emptyset \), d.h. die Mengen haben kein gemeinsames Element.

Eine Produktion hat die Gestalt $$ \text{...linke Seite...} \rightarrow \text{...rechte Seite...}, $$ wobei die Zeichenfolge linke Seite ersetzt wird durch rechte Seite.

Beispiel

Gegeben ist die Grammatik \( G = ( N, T, P, S)\) mit

• \( N = \{ S, A, B \} \),
• \( T = \{ a, b \} \),
• \( P = \{ S \overset{1}{\rightarrow} A, \quad A \overset{2}{\rightarrow} aB, \quad B \overset{3}{\rightarrow} Ab, \quad B \overset{4}{\rightarrow} b \} \) und
• dem Startsymbol \( S \).

Eine Ableitung beginnt stets mit dem Startsymbol und endet mit einem Wort bestehend aus Terminalen. $$ S \overset{1}{\rightarrow} {\color{red}A} \overset{2}{\rightarrow} {\color{red} aB} \overset{3}{\rightarrow} a{\color{red}Ab} \overset{2}{\rightarrow} a{\color{red}aB}b \overset{4}{\rightarrow} aa{\color{red}b}b $$ Alle Wörter, die unter Anwendung der Produktionen abgeleitet werden können, gehören zu der von der Grammatik erzeugten Sprache \( L(G) \).

Durch Probieren sind schnell die ersten Wörter der Sprache erzeugt: \( ab, aabb, aaabbb, aaaabbbb, ...\)

Die Sprache \( L(G) \) lässt sich dann formal angeben mit $$ L(G) = \{ \; a^n b^n \; | \; n \geq 1 \; \}. $$

S

Produktionsregeln:
Regel 1: S \(\rightarrow\) aA
Regel 2: A \(\rightarrow\) aA
Regel 3: A \(\rightarrow\) aB
Regel 4: B \(\rightarrow\) bB
Regel 5: B \(\rightarrow\) b
Neustart

Aufgaben

a) Überprüfen Sie, ob die Wörter aaabb, abab, ab und aaabbb durch die Grammatik \( G \) erzeugt werden können. Geben Sie hierzu jeweils die dazugehörige Ableitung (d.h., die Reihenfolge Ihrer benutzten Regeln) an.

b) Geben Sie das kürzeste Wort an, das mit der Grammatik produziert werden kann.

c) Geben Sie die formale Definition der Grammatik \( G \) an.

d) Beschreiben Sie die von der Grammatik erzeugten Sprache \( L(G) \) mit eigenen Worten.

Expertenaufgabe

e) Die Produktionen von \( G \) können reduziert werden. Vereinfachen Sie \( G \), ohne die von ihr erzeugte Sprache \( L(G) \) zu verändern.

Auf der ganzen Welt lachen Menschen und das ist gut, denn Lachen ist gesund. Die meisten Menschen erzeugen beim Lachen Silben wie ha, he bzw. ho. Die haha-Sprache \( L \) enthält alle Wörter, die aus ha, he bzw. ho gebildet werden können und auf haha enden.

Aufgaben

a) Erstellen Sie die Produktionen P einer Grammatik \( G = (N, T, P, S) \) mit \( T = \{ha, he, ho\} \) und dem Startzustand \( S \). Ergänzen Sie hierbei um die Menge der Nichtterminalsymbole \( N \). Die Grammatik soll die Wörter der haha-Sprache erzeugen können.

b) Überprüfen Sie, ob Ihre Grammatik tatsächlich nur Wörter der haha-Sprache erkennt.

c) Geben Sie an, wie viele Wörter die haha-Sprache enthält.

S

Produktionsregeln P:
Regel 1: S \(\rightarrow\) aSBC
Regel 2: S \(\rightarrow\) aBC
Regel 3: CB \(\rightarrow\) BC
Regel 4: aB \(\rightarrow\) ab
Regel 5: bB \(\rightarrow\) bb
Regel 6: bC \(\rightarrow\) bc
Regel 7: cC \(\rightarrow\) cc
Neustart

Die Grammatik \( G \) ist gegeben als \( G = (N, T, P, S) \) mit \( N = \{S, B, C\}, T = \{a, b, c\} \), den Produktionen \( P \) und dem Startsymbol \( S \).

Aufgaben

a) Geben Sie mind. zwei Wörter an, die mit Hilfe der Grammatik \( G \) erzeugt werden können und stellen Sie deren Ableitung nachvollziehbar dar.

b) Beschreiben Sie die von der Grammatik erzeugten Sprache \( L(G) \) mit eigenen Worten. Versuchen Sie dann auch die Sprache formal anzugeben.

Expertenaufgabe

c) Finden Sie durch Anwendung der Produktionen eine Ableitung, für welche die Grammatik keine Folgeregel aufweist?

Palindrome sind Wörter, die von vorn und hinten gelesen identisch sind. Typische Vertreter sind ANNA, OTTO oder gar RELIEFPFEILER.

Aufgabe

Geben Sie eine Grammatik an, die alle Palindrome über dem Terminalalphabet \( T = \{a, b\} \) erzeugen kann.

Tipp 1: Verschaffen Sie sich zunächst einen Überblick über mögliche Palindrome.

Tipp 2: Sie benötigen nur fünf Produktionen.

Tipp 3: Sie benötigen nur das Nichtterminalsymbol \( S\) .