Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in SPR-AD

Gilt ii. auch für EA und KA

Wed, 22 Oct 2014 14:42:27 +0000

"Jede beliebige Menge von Wörtern ist Sprache einer Turingmaschine." --> FALSCH
Wie sieht das bei EA und KA aus? Für EA's müsste es auch falsch sein, für KA's richtig?

Dann noch etwas. Es gilt ja:
L3 ( L2 ( L1 ( L0
"alle endlichen Mengen von Wörtern": beinhaltet das ALLES außer eine unendliche Sprache?
Und wenn EA's, KA's, LBA's und TM's bzw. L3, L2, L1 und L0 "alle endlichen Mengen von Wörtern" (also alles außer unendliche Sprache?) erkennen bzw. ausdrücken können, was können dann die Typen mit niedrigerem i ausdrücken, was die Typen mit höherem i nicht können?

Wie ist bei det und ndet?

Wed, 22 Oct 2014 14:40:01 +0000

und mit det und ndet gilt dann?

L detEA ( L ndetEA ( netLKA (dnetLKA (LdetTM (LndetTM ?

Nachfrage zur Sprachmächtigkeit

Wed, 22 Oct 2014 14:38:01 +0000

Ich hab das mit der Sprachmächtigkeit immernoch nicht so ganz verstanden und aus den Vorlesungsfolien werde ich da auch nicht wirklich schlau.

"Det EA sind nicht mächtiger als ndet EA. Mit Sprachmächtigkeit ist gemeint, wie viele unterschiedliche Sprachen erkannt werden können."

und in der Lösung ist steht auch "ndet.EA sind nicht mächtiger als Det EA".

Wann ist denn jetzt ein Automat mächtiger als der andere?

Kann man hier auch so eine Abstufung machen mit .. ist mächstiger als *** ist mächtiger als +++?

Wie sieht das mit der Mächtigkeit bei TM und KA aus?!

was passiert mit einem Wort der Form a^n b^n c^n ?

Wed, 22 Oct 2014 14:34:51 +0000

Mir ist auch nicht klar, was mit einem Wort der Form a^n b^n c^n passiert.

Die Menge: (aaabbbccc, aaaabbbbcccc) wäre doch eine endliche Menge von Wörtern, oder nicht?
Ein KA kann doch diese Wörter aber nicht erkennen!?

Erkennen auch andere Automaten alle endlichen Mengen von Wörtern?

Wed, 22 Oct 2014 14:32:21 +0000

zu i) Alle endlichen Mengen von Wörtern sind Sprachen eines Kellerautomaten.

Gilt das auch für Turing-Maschinen und ndet. linear beschränkte TM? Was ist mit endlichen Automaten?

Erklärug der Lösung zu i. und ii.

Wed, 22 Oct 2014 14:29:10 +0000

Könnte mir jemand bitte die Frage i und ii erklären? Warum die Antwort so ist, wie sie ist?