Übungen
Aufgabe 1
Viele Programmier- und Auszeichnungssprachen können durch eine kontextfreie Grammatik beschrieben werden. Damit können sie auch durch einen Kellerautomaten erkannt werden. Das soll hier am Beispiel einer vereinfachten HTML-Variante "EasyHTML" gezeigt werden.
Beachte: EasyHTML unterscheidet sich von der in den folgenden Abschnitten betrachteten Sprache MyXML dahingehend, dass es hier nur endlich viele Tags gibt. Sie ist ein endlicher Spezialfall von MyXML. Daher kann EasyHTML noch von einem Kellerautomaten erkannt werden, während das für MyXML nicht mehr möglich ist.
Der folgende Quelltext zeigt ein Easy-HTML-Dokument.
<HTML>
<B>aaa<BR/>a</B>
<OL>
<LI>a</LI>
<LI><B>a</B></LI>
</OL>
</HTML>
Etwas kompakter lässt sich dieses Dokument so darstellen:
<HTML><B>aaa<BR/>a</B><OL><LI>a</LI><LI><B>a</B></LI></OL></HTML>
Die folgende Grammatik beschreibt den Aufbau korrekt gebildeter Easy-HTML-Dokumente.
HTMLDoc -> <HTML> Doc </HTML> Doc -> λ | Elem Doc Elem -> Text | <BR/> | <B> Doc </B> | <OL> List </OL> List -> λ | ListItem List ListItem -> <LI> Doc </LI> Text -> λ | Char Text Char -> a
(a) Bestimme zunächst die Menge der Terminal- und die Menge der Nonterminalsymbole der gegebenen Grammatik.
(b) Zeige (z.B. mit einem Ableitungsbaum), dass das folgende Wort mit der Grammatik ableitbar ist.
<HTML>a<B>aa<BR/>a</B><OL><LI>a</LI><LI><B>aa</B></LI></OL></HTML>
(c) Erzeuge selbst weitere Wörter, die (nicht) zur Sprache EasyHTML gehören.
accept
<HTML>a</HTML>
<HTML><OL></OL></HTML>
<HTML><B>a</B></HTML>
<HTML><OL><LI>a</LI><LI>aa</LI></OL></HTML>
<HTML><OL><LI>a</LI><LI>aa</LI></OL><OL><LI>a</LI><LI>aa</LI></OL></HTML>
<HTML><OL><OL><LI>a</LI><LI>aa</LI></OL><LI>aaa</LI></OL></HTML>
...
reject
<HTML>
<HTML><B>a</B>
<HTML></B>a<B></HTML>
<HTML><B>a</HTML>
<HTML><OL><LI>a</LI></HTML>
<HTML><OL><LI>a<LI>a</LI></LI></OL></HTML>
...
(d) Begründe, dass die Sprache EasyHTML kontextfrei ist.
(e) Nun soll ein Kellerautomat zur Erkennung von EasyHTML entwickelt werden. Beginne mit einer vereinfachten Variante von EasyHTML, die auf Listen verzichtet.
(f) Erweitere den Kellerautomaten aus (e) um Listen. Beachte, dass LI-Elemente nur innerhalb eines OL-Elements auftauchen dürfen. Beachte auch, dass innerhalb eines LI-Elements wieder andere Elemente - also auch wieder Listen - auftreten können. Benutze zum Testen die Wörter aus (c).
(g) (Zusatz für Profis) Ergänze die Grammatik und den Kellerautomaten um die Möglichkeit, öffnende OL-Tags mit den Attributen TYPE = ( 1 | A | i) und START = (Zahl) zu ergänzen. Diese dürfen jeweils nur einmal auftauchen. Beispiel:
<OL TYPE=1 START=3>...</OL>
Aufgabe 2
Entscheide mit Hilfe des Kellerautomaten, ob die folgenden Sprachen kontextfrei sind. Wenn die Sprache kontextfrei ist, dann gib einen passenden Kellerautomaten an. Falls nicht, dann begründe, warum diese nicht mit einem Kellerautomaten erkannt werden kann.
(a) L = {anbn | n ≥ 0}
(b) L = {anbncn | n ≥ 0}
(c) L = {anbm | n ≥ m ≥ 0}
(d) L = {w ∈ {a, b}* | #a = #b}
(e) L = {w ∈ {a, b, c}* | #a = #b = #c}
(f) L = {anbmcn | n, m ≥ 0}
Hinweis: #a bezeichnet die Anzahl der a´s in dem betreffenden Wort.
Aufgabe 3
Gegeben ist eine Grammatik G = ({S, A, B, C}, {a, b, c}, S, P) mit den folgenden Produktionen:
S → aBC | bBBCC | aACCA
A → a
B → b | aAB
C → c
(a) Entwickle selbst einen Kellerautomaten, der die von G erzeugte Sprache L(G) erkennt.
(b) Man kann auch automatisiert einen Kellerautomaten zur Sprache L(G) erzeugen. Probiere das mit Jflap aus.
