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

Beantwortet: Gilt ii. auch für EA und KA

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

Die Menge der Sprachen, die man mit einer TM erkennen kann, ist eine echte Obermenge der Sprachen, die man mit einem Kellerautomaten erkennen kann (was wiederum eine echte Obermenge der Sprachen, die man mit einem EA erkennen kann, ist). Die Aussage

"Jede beliebige Menge von Wörtern ist Sprache einer *"

ist daher auch für endliche Automaten und Kellerautomaten falsch.

Eine "endlichen Mengen von Wörtern" ist beispielsweise die Menge aller Wörter, die in diesem Post vorkommen oder alle Wörter, die im Duden stehen. Dagegen sind die meisten Sprachen, die in der Vorlesung oder den Aufgaben vorkommen, keine endliche Menge von Wörtern. Beispielsweise gibt es unendlich viele Wörter, die in der Sprache aller Wörter, die aus 0en und 1en bestehen und auf 1 enden, liegen (z.B. 01, 001, 0001, 00001, ...)

Die unterschiedliche Mächtigkeit von EA, KA und TM zeigt sich erst bei solchen Sprachen.

So eine endliche Menge von Wörtern zu erkennen, ist ziemlich einfach. Da es nur endlich viele Wörter in der Sprache gibt, kann man einfach die Eingabe mit jedem der Wörter der Sprache vergleichen (das ist auch mit einem EA möglich)

Gruß,

Tobias (Tutor)

Beantwortet: Wie ist bei det und ndet?

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

Hallo,

das hängt davon ab, welche Automaten du betrachtest. Bei EA und TM ist die Mächtigkeit unabhängig vom Determinismus. Lediglich die Mächtigkeit des nichtdet. KA ist größer als die des det. KA.

Somit gilt L detEA = L ndetEA ( L detKA ( L ndetKA ( L detTM = L ndetTM

Mächtigkeit bedeutet in diesem Kontext z.B., dass die Menge der Sprachen, die von einem EA erkannt werden kann, eine Teilmenge der Sprachen ist, die von einem KA erkannt werden kann.

Viele Grüße

Philippe (Tutor)

Beantwortet: Nachfrage zur Sprachmächtigkeit

Wed, 22 Oct 2014 14:39:05 +0000

Hallo,

was du sagen ist : "(" Bedeutet jetzt mal Teilmenge von

L EA ( LKA ( LTM

In Worten: Die Sprachmächtigkeit von Endlichen Automaten ist eine Teilmenge von den Kellerautomaten und diese sind wieder Teilmenge von den Turingmaschinen.

Grüße,

Jördis ( Tutorin )

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

Wed, 22 Oct 2014 14:36:28 +0000

Richtig, die von dir angegebene Menge ist eine endliche Menge von Wörtern. Diese Sprache, die nur aus zwei Wörtern besteht, kann von einem KA erkannt werden, indem man das oben beschriebene Verfahren nutzt.

Die Sprache a^n b^n c^n mit n element N ist aber keine endliche Menge und kann von einem Kellerautomaten nicht erkannt werden (Beweis PPL).

Sven (Tutor)

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

Wed, 22 Oct 2014 14:33:19 +0000

Hallo,

"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?"

da eine Turingmaschine einen Kellerautomaten simulieren kann, gilt dies natürlich auch Turingmaschinen.

Für einen endlichen AUtomaten gilt dies aber auch, da ich bei einer endlichen Menge von Wörtern im Zweifelsfall für jedes Wort einen separaten Zustandsabfolge angeben könnte (ist zuerst nichtdeterministisch, kann aber auch in einen deterministischen Automaten umgewandelt werden).

Freundliche Grüße
Friederike Pfeiffer

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

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

i) Für ein Wort aus einer endlichen Menge von Wörtern kann man sich immer einen Kellerautomaten definieren, der genau dieses Wort erkennt, indem man die Zustände speziell auf dieses eine Wort abstimmt. Da es sich um eine endliche Menge handelt, kann man das theoretisch für jedes Wort aus der Menge so machen. Der enstehende Kellerautomat hat dann sehr viele (aber endlich viele) Zustände und ist nicht-deterministisch.

ii) Es gibt Sprachen, die nicht in L0 liegen und somit auch nicht von einer TM erkannt werden können (siehe dazu Diagramm von Folie 5-31).

Viele Grüße,

Sven (Tutor)