Suche Home Einstellungen Anmelden Hilfe  

Q1  (4 points)

Ordnen Sie den folgenden Sprachen jeweils die kleinste Sprachklasse zu, die sie enthält.
Als Sprachklassen gelten "regulär", "linear", "kontextfrei", "kontextsensitiv", "Ch-0".
  1. {a1k1b1k1a2k2b2k2...amkmbmkm | kj aus IN0 für alle j aus {1,...,m}}
  2. {2p | p Primzahl}
  3. {www | w aus {0}*}
  4. {Kontext}
  5. {akblcm | k>=l>=m>=0}

  6. {w1|w|wR | w aus {0,1}*}
Q2  (4 points)
Welches Kennzeichen des Kellerautomaten (Push-down-Akzeptors) sorgt für eine gegenüber dem endlichen Akzeptor höhere Sprachakzeptanzfähigkeit?
Answer:

Q3  (5 points)
Welche Sprachklasse wird von Kellerautomaten akzeptiert, wenn man den Keller in der Höhe beschränkt?
1. Reguläre Sprachen 
2. Lineare Sprachen 
3. Kontextfreie Sprachen 
4. Kontextsensitive Sprachen 
5. Typ-0-Sprachen 
6. keine der genannten Klassen 

Q4  (3 points)
Welche der folgenden Behauptungen ist wahr?
1. Das Komplement einer regulären Sprache ist kontextfrei. 
2. Das Komplement einer kontextfreien Sprache ist kontextfrei. 
3. Das Komplement einer deterministisch kontextfreien Sprache ist kontextfrei. 
4. Das Komplement einer deterministisch kontextfreien Sprache ist deterministisch kontextfrei. 

Q5  (4 points)
Welche der folgenden Aussagen sind wahr?
1. Alle kontextfreien Sprachen werden von deterministischen Kellerautomaten erkannt. 
2. Alle kontextfreien Sprachen werden von nichtdeterministischen Kellerautomaten erkannt. 
3. Alle kontextfreien Sprachen werden von deterministischen Kellerautomaten mit leerem Keller erkannt. 
4. Alle kontextfreien Sprachen werden von nichtdeterministischen Kellerautomaten mit leerem Keller erkannt. 

Q6  (7 points)
Seien R und R' reguläre Ausdrücke.
Dann gilt:

1. Das ist richtig. 
2. Das ist falsch. 

 

Benutzer: gast • Besitzer: mthomas • Zuletzt geändert am: