Theoretische Informatik: Quiz zu Automaten & Sprachen
Eingeordnet in Lehre und Ausbildung
Geschrieben am 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 | 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 |