Theoretische Informatik: Quiz zu Automaten & Sprachen

Geschrieben am 11. Januar 2026 in Deutsch mit einer Größe von 10,23 KB

Wahre Aussagen zur Theoretischen Informatik

Welche der folgenden Aussagen sind wahr?

Ja	Nein		Ja	Nein
	x	Für gewisse NFA gibt es keinen äquivalenten DFA.	x		Jedes Loop-Programm ist ein While-Programm.
	x	Endliche Automaten haben nur endlich viele Zustände, aber Kellerautomaten können auch unendlich viele Zustände haben.		x	Jede reguläre Sprache ist eine endliche Sprache.
x		Das Komplement einer von einem LBA erkennbaren Sprache kann stets durch einen LBA erkannt werden.		x	Jede totale Funktion ist LOOP-berechenbar.
x		Es gibt totale Markov-berechenbare Funktionen, die nicht primitiv-rekursiv sind.	x		Alle LOOP-berechenbaren Funktionen sind total.
	x	Es gibt partiell-rekursive Funktionen, die nicht Turing-berechenbar sind.	x		Die Klasse der kontextfreien Sprachen ist abgeschlossen unter Vereinigung, Spiegelung, Konkatenation, Kleene'scher Hüllenbildung und Anwendung der Homomorphismen.
x		Die Nummernmenge einer jeden nicht-trivialen Eigenschaft partiell-rekursiver Funktionen ist unentscheidbar.		x	Die Klasse der kontextfreien Sprachen ist abgeschlossen unter Durchschnitt, Komplement und symmetrischer Differenz.
x		L₁ = {aⁿbⁿ \| n ≥ 1} ist kontextfrei, aber nicht regulär.
x		∅ ≠ {λ}
x		Die Spiegelung jeder regulären Sprache ist regulär.
	x	Jede von einem DFA akzeptierte Sprache ist endlich.
	x	Mit dem Pumping-Lemma für reguläre Sprachen kann man nachweisen, dass eine Sprache nicht kontextfrei ist.
x		Der Äquivalenzklassenautomat ist immer minimal.
	x	Die Klasse der kontextfreien Sprachen ist unter Komplementbildung abgeschlossen.
	x	Jede deterministisch-kontextfreie Sprache ist regulär.
x		Jede endliche Sprache ist regulär.
x		Jeder reguläre Ausdruck beschreibt genau eine Sprache.
	x	Jede GOTO-berechenbare Funktion ist LOOP-berechenbar.
x		Jede primitiv-rekursive Funktion ist total.
x		Jede While-berechenbare Funktion ist auch Turing-berechenbar.
x		Somit sind LOOP-berechenbare Funktionen stets total.
x		Es ist nicht möglich, mit einem LOOP-Programm unendliche Schleifen zu programmieren.
	x	RE oder CF ist abgeschlossen unter Komplementbildung.
	x	Jedes While-Programm ist ein Loop-Programm.

Wahre Aussagen zur Theoretischen Informatik

Verwandte Einträge: