Selbsttest

1.1  Wann akzeptiert ein DEA ein Wort?

1.2  Ein vollständiger DEA hat 5 Zustände und |Σ| = 3. Wie viele Übergänge?

1.3  Was bedeutet „deterministisch“?

1.4  Wann darf der Fehlerzustand im Graphen fehlen?

1.5  Was ist ε?

1.6  Wozu dient die Bedeutung eines Zustands?

1.7  Welche Java-Zeile setzt einen Tabellenautomaten weiter?

1.8  Was passiert ohne „zustand = 0;“ am Anfang von akzeptiert?

2.1  Wie ist ein Mealy-Übergang beschriftet?

2.2  Was bedeutet „a / ε“?

2.3  Hat ein Mealy-Automat Endzustände?

2.4  Ω bezeichnet …

2.5  Ein DEA hat 4 Zustände. Wie viele Vorgeschichten aⁱ unterscheidet er höchstens?

2.6  Welche Sprache erkennt ein DEA?

2.7  Welche Sprache ist regulär?

2.8  Worauf beruht der Nachweis, dass kein DEA {aⁿbⁿ} erkennt?

3.1  Was bedeutet der Übergang (A,b):ε?

3.2  Nach (#,a):A# liegt oben …

3.3  Was liegt beim Start im Keller?

3.4  Wann akzeptiert ein Kellerautomat?

3.5  Wozu dient (#,ε):# in den Endzustand?

3.6  Keller eines aⁿbⁿ-Automaten nach „aaab“ (oben links)?

3.7  Was ist bei einem deterministischen Kellerautomaten verboten?

3.8  Welche Sprache erkennt ein Kellerautomat, aber kein DEA?

4.1  Wie viele Wörter der Länge 3 gibt es über {a, b}?

4.2  Was gehört nicht zur Angabe einer Grammatik?

4.3  Was ist eine Satzform?

4.4  S → aS | b erzeugt …

4.5  Wofür steht der Strich | in S → aA | b?

4.6  Wie liest man den Ableitungsbaum?

4.7  Was bedeutet S ⇒* w?

4.8  Syntax beschreibt …

5.1  Welche Regel ist regulär?

5.2  Aus einem DEA-Pfeil z1 –a→ z2 wird die Regel …

5.3  Ein Endzustand Z wird zur Regel …

5.4  Die Regel A → a wird im DEA zu …

5.5  Kontextfrei heißt …

5.6  S → aSb | ε erzeugt …

5.7  Eine Grammatik ist mehrdeutig, wenn …

5.8  Welche Sprache ist nicht kontextfrei?