Fachrat Informatik - Forum

Quoted

Original von MAX
Abschlußeigenschaften:

1)CSL
Spiegelung: ???

Ja, ein LBA kann ja einfach die Eingabe spiegeln (z. B. zeichenweise von außen nach innen) und dann den ursprünglichen Algorithmus verwenden.

Quoted

2)Typ-0 Sprachen
Spiegelung: ???

Was ein LBA kann, kann eine TM erst recht.

Quoted

Homomorphismus und inverser Hom.: ???

Homomorphismus ist klar, da hier nur Ersetzungsregeln auf den Nichtterminalen der Grammatik angewandt werden. Dadurch bleibt eine Sprache natürlich vom Typ 0. (Wenn man vorher eine Normalform herbeiführt, in der auf jeder linken Regelseite mindestens ein Nichtterminal steht.)

Inverser Homomorphismus. Algorithmus: Rate ein Wort beliebiger Länge und prüfe, ob dessen Abbildung unter dem Homomorphismus ein Wort der Ausgangssprache ist. Dies ist ein Semi-Entscheidungsalgorithmus, also ist die erkannte Sprache vom Typ 0.

Quoted

Original von mtx
2)CSL
Endlichkeitsproblem: nicht entscheidbar (siehe Satz von Rice)
Nicht leeres Komplement: nicht entscheidbar ( " )

Wieso sich das aus dem Satz von Rice ergibt, sehe ich gerade nicht. Dieser macht ja keine Aussage über platzbeschränkte Berechnungen.

Für das CSL-Endlichkeitsproblem (was ich im folgenden als CSLFIN bezeichne, also die Menge aller Kodierungen von Turingmaschinen, die linear platzbeschränkt sind und nur eine endliche Menge von Wörtern akzeptieren) läßt sich jedoch eine Reduktion vom speziellen Halteproblem angeben. Die Reduktion funktioniert mit der wie folgt definierten Funktion f:

Für alle w sei M_{f(w)} eine (beliebige) linear platzbeschränkte TM, die ihre Eingabe vom Band löscht, dann M_w auf Eingabe w simuliert, und genau dann akzeptiert, wenn die Simulation mehr Rechenschritte erfordert als Bandzellen verfügbar sind (dies läßt sich mittels Markierung der Bandzellen ermitteln). (Falls der Platz auf dem Band bereits für den Simulationsmechanismus nicht ausreicht, so lehne ab.)

Ist w \in K, so wird M_{f(w)} ab einer bestimmten Eingabegröße (die Rechenzeit von M_w auf Eingabe w) immer ablehnen. Damit ist f(w) \in CSLFIN.

Ist w \notin K, so wird M_{f(w)} ab einer bestimmten Eingabegröße (die der Simulationsmechnismus benötigt) immer akzeptieren. Damit ist f(w) \notin CSLFIN.