Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Frage zu Kontextsensitiven Sprachen.
Wenn eine sprache kontextsensitiv ist, dann isse ja auch turingentscheidbar. Reicht es da denn die funktiionsweise dieser Tm zu beschreiben? Oder muss man das immer formal machen, mit so einem Turingautomat.
Kommt halt drauf an, wie die Frage gestellt ist. Lautet sie “zeigen Sie, daß L kontextsensitiv ist” , könntest Du eine Typ-1-Grammatik angeben. Oder einen NLBA (einen (nichtdeterministisch) linear bandbeschränkten Automaten).
Wenn Du nur die Funktionsweise der TM beschreiben willst, solltest Du darauf achten, daß sie nicht über die Grenzen des Inputwortes hinausschreibt. Letzteres solltest Du auch zeigen, zumindest glaubhaft machen.
Wenn Du faul und bequem bist, kannste auch ne k-Band-TM beschreiben, denn die ist durch ne 1-Band-TM simulierbar, die nicht mehr Platz benötigt als die k-Band-TM.
was ist denn touringendscheidbar?
nur das es für die sprache einen NLBA bzw. TM mit endlichen band gibt oder noch mehr?
sind NLBA’s äquivalent mit TM mit endlichen band oder muss es schon eine nichtdeterministische TM mit endlichem band sein?
-
Turing-entscheidbar, nicht touringentscheidbar
-
turingentscheidbar heißt, daß Du einen Algorithmus schreiben kannst, der nicht Dein Problem entscheidet und immer terminiert, d.h. es gibt eine TM, die das Problem entscheidet, also immer hält.
-
was heißt “TM mit endlichem Band”? Eine TM, die terminiert, braucht natürlich nur endlich viel Speicher. Wenn das Band aber endlich ist, d.h. begrenzt, und zwar durch eine Konstante, für alle Inputwörter, dann hast Du einen endlichen Automaten (weil Du das endliche Band im Zustand kodieren kannst). Ist aber nicht wichtig, also vergiß Punkt 3)
-
Ein LBA, bzw. NLBA darf nicht über die Grenzen des Inputwortes hinausschreiben. Eine TM darf das sehr wohl.