10 questions🇩🇪Deutsch
🤖 Endliche Automaten – Oberstufe
Informatik · Oberstufe — Zustandsdiagramme lesen, akzeptierte Wörter prüfen sowie Grammatiken und reguläre Sprachen
Make it your own private quiz and change anything you like
Questions
Welche Komponente eines DEA legt fest, in welchen Zustand er beim Lesen eines Zeichens wechselt?
Die Überführungsfunktion δ
Der Startzustand q₀
Die Menge der Endzustände F
Das Eingabealphabet Σ
20s
Wann akzeptiert ein DEA ein Eingabewort?
Wenn er nach dem letzten Zeichen in einem Endzustand ist
Wenn er nach dem ersten Zeichen in einem Endzustand ist
Wenn er jeden Zustand mindestens einmal besucht
Wenn er unterwegs einmal einen Endzustand erreicht
20s
Wie viele Startzustände besitzt ein deterministischer endlicher Automat?
Genau zwei
Genau einen
Beliebig viele
So viele wie Endzustände
20s
Welches Wort passt zum regulären Ausdruck a(b|c)*a?
acbba
baca
abaca
abcb
30s
Ein DEA über {0,1}: q₀ ist Start- und Endzustand, q₁ nicht. Bei 0 bleibt er im Zustand, bei 1 wechselt er. Was akzeptiert er?
Alle Wörter, die auf 0 enden
Alle Wörter mit gerader Länge
Alle Wörter mit gerader Anzahl von Einsen
Alle Wörter mit ungerader Anzahl von Einsen
30s
δ(q₀,a)=q₁, δ(q₀,b)=q₀, δ(q₁,a)=q₁, δ(q₁,b)=q₂, δ(q₂,a)=q₁, δ(q₂,b)=q₀. Start q₀. Wo endet das Wort „abba“?
In q₂
In q₁
Nirgends, δ ist undefiniert
In q₀
30s
Welche Aussage über nichtdeterministische (NEA) und deterministische endliche Automaten (DEA) ist korrekt?
Ein NEA hat stets weniger Zustände als ein DEA
NEA können die Sprache aⁿbⁿ erkennen
NEA erkennen auch nicht reguläre Sprachen
Zu jedem NEA gibt es einen äquivalenten DEA
30s
Ein NEA hat 4 Zustände. Wie viele Zustände hat der per Potenzmengenkonstruktion erzeugte DEA höchstens?
12
8
24
16
30s
Gegeben ist die reguläre Grammatik S → aS | bA und A → bA | b. Welches Wort ist ableitbar?
abba
bab
ab
aabb
30s
Warum kann kein endlicher Automat die Sprache L = {aⁿbⁿ | n ≥ 1} erkennen?
Das Alphabet {a, b} hat zu wenige Zeichen
Er kann sich keine beliebig große Anzahl von a merken
Ein endlicher Automat darf nur einen Endzustand haben
Die Sprache enthält unendlich viele Wörter
30s