http://www.oelinger.de     Oelinger Home

Home Maria Oelinger     Hilfe 

zurück zur Übersicht

Prüfungsprotokoll Automatentheorie

Hauptdiplomprüfung Theoretische Informatik

Fach: Automaten und formale Sprachen
Prüfer: Dr. X. Zhou, Universität Duisburg
Datum: 12.04.2000
Dauer: ca. 25 Min
Note: 1.3

Fragenkatalog:
1. Erzählen Sie etwas über Grammatiken. Definition, Chomsky-Hierarchie mit Eigenschaften der einzelnen Grammatiken.

 

2. Welche Automatenmodelle gehören dazu? (Nur einen Überblick, bitte.) TM (Typ 0), LBA (Typ 1), DKA (LR), NKA (Typ 2), DFA, NFA, ZWA (Typ 3).

 

3. Definieren Sie DFA, NFA, Zwei-Wege-Automat (ZWA). Definitionen, keine Beispiele gefragt.

 

4. Was ist der Unterschied zwischen DFA und ZWA? DFA arbeitet von links nach rechts, ZWA kann in beide Richtungen laufen.

 

5. Ist "keine Bewegung" eine Möglichkeit für ZWA? Nein.

 
6. Definieren Sie den Kellerautomat. NKA mit Überführungsfunktion.

 

7. Was ist der Unterschied zum DKA? Entweder ist er für ein Zeichen aus dem Alphabet definiert oder für das leere Wort epsilon oder überhaupt nicht.

 

8. Können Sie die Maschine skizzieren? Ja, für delta (z, a, A) enthält (z', B1...Bm) Arbeitsweise erläutern.

 

9. Was sind die Normalformen für kfS? CNF mit Regeln, wo eine Variable auf ein Terminal oder ein Terminal vor einer Variable führt und GNF, wo eine Variable auf genau ein Terminal, gefolgt von beliebig vielen Variablen, führt.

 

10. Wozu braucht man die Normalformen? CNF: Syntaxbaum, Beweis von Pumping-Lemma und Ogdens Lemma, CYK-Algorithmus; Aufwand ist O(|V| • S(G)), S(G) ist die Gesamtzahl aller Terminale und Variable in P für kfG G = (V, SIGMA, P, S).
GNF: Kellerautomaten.

 

11. Was ist eine LR(0)-Grammatik? Kontextfreie Grammatik G mit den Eigenschaften:
  1. Starsymbol S steht nicht auf der rechten Seite der Produktionen.
  2. Für jedes lebensfähige Prüfix gamma von G gilt:
    Ist A —> alpha • vollständiges und für gamma gültiges Element, dann gibt es kein anderes vollständiges Element und kein Element mit einem Terminal rechts des Punktes, das für gamma gültig ist.

 

zurück zur Übersicht

Feel free to send me email: maria@oelinger.de

© 2000 Maria Oelinger
cand. math. 		Prüfungsprotokoll Letzte Änderung: 07.06.2000
address: http://www.oelinger.de/maria/automat/protokoll.htm