Logo des digitalen Schulbuchs inf-schule.de. Schriftzug in Zustandsübergangsdiagramm eines endlichen Automaten.

KIDS

Übungen

Aufgabe 1

Jede Programmier- und Auszeichnungssprache kann durch eine kontextfreie Grammatik beschrieben werden. Damit kann sie auch durch einen Kellerautomaten erkannt werden. Das soll hier am Beispiel einer vereinfachten HTML-Variante "EasyHTML" gezeigt werden.

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.

X

Fehler melden

X

Suche