Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Berechenbarkeitstheorie » Beweis: Rekursiv aufzählbare Sprachen (Aufzählmaschine)
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Beweis: Rekursiv aufzählbare Sprachen (Aufzählmaschine)
Mauzi
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.06.2020
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-06-19


Hallo,
ich habe folgende Aufgabe gegeben:

Eine Aufzählmaschine ist definiert wie eine Turingmaschine mit
zwei Bändern: einem Arbeitsband und einem Ausgabeband, auf das nur geschrieben werden kann. Der Kopf des Ausgabebandes bewegt sich nach rechts, wenn er ein Symbol aus dem Alphabet $\sum$ schreibt; andere Aktionen sind für ihn nicht möglich.
Die Maschine beginnt im Anfangszustand mit leeren Bändern. Sie hat einen ausgezeichneten Aufzählzustand q_#. Wird dieser erreicht, so wird der Inhalt des Ausgabebandes ausgegeben, wir sagen auch aufgezählt. Das Ausgabeband wird dann automatisch gelöscht, und sein Kopf auf die Startposition zurückgesetzt. Dann rechnet die Maschine mit dem aktuellen Inhalt des Arbeitsbandes weiter, im allgemeinen ohne je anzuhalten.
Die Sprache L(A) eines solchen Aufzählers A ist die Menge aller Wörter aus $\sum$* die durch A irgendwann aufgezählt werden. Ein und dasselbe Wort kann dabei mehrmals aufgezählt werden.

Beweist folgende Aussage:
Die Familie der Sprachen, die durch Aufzählmaschinen aufgezählt werden ist
genau die Familie der rekursiv aufzählbaren/semi-entscheidbaren Sprachen.

Ich bin mir nun aber nicht sicher, wie ich Beweisen soll dass die Familie der Sprachen, die aufgezählt werden, genau die Familie der rekursiv aufzählbaren Sprachen ist, denn durch die Aufgabenstellung und der Definition von aufzählbaren Sprachen ist doch klar, dass die aufgezählten Sprachen rekursiv aufzählbar sind.

Eine Sprache L heißt erkennbar, rekursiv aufzählbar oder semi-entscheidbar, wenn es eine Turingmaschine M gibt, die L erkennt, d.h.
es gilt L = L(M).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 903
Wohnort: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-06-19


Hallo Mauzi, und willkommen auf dem Matheplaneten!

Du könntest so anfangen:

Behauptung. Die Klasse der r.a. Sprachen ist gleich der Klasse der Sprachen, die durch Aufzählmaschinen aufgezählt werden.

Beweis. Sei \(L\) eine Sprache.


  1. Zunächst gelte: \(L\) ist r.a. Zeige dann, dass es einen Aufzähler gibt, der \(L\) aufzählt. Konstruiere einen.



  2. Nun gelte: Es gibt einen Aufzähler \(E\) für \(L\). Zeige dann, dass \(L\) r.a. ist. Durch einen Algorithmus, der entfernte Ähnlichkeit mit beschränkter Tiefensuche hat und dessen Fachterminus mir gerade nicht einfallen will.




Hilft dir das?

mfg
thureduehrsen


-----------------
sammeltlemmas.blogspot.de/

https://www.informatik.uni-kiel.de/~tdu/



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Mauzi
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.06.2020
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-06-19


Hallo thureduehrsen,

Ja ich denke das hilft mir weiter. Ich muss zwar noch ein wenig Zeit investieren, aber im Grundsatz verstehe ich was Sie meinen.👍

Vielen Dank! 🤗



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 903
Wohnort: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-06-19


Hallo Mauzi,

ich hoffe, dass diese Aufgabe nicht bereits in wenigen Tagen abzugeben ist. Die Freude an der erfolgreichen Lösung der Aufgabe sollte eine längere Nachwirkung haben.

mfg
thureduehrsen

P.S. Wir duzen uns hier alle.
Willkommen im Forum!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Mauzi
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.06.2020
Mitteilungen: 3
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-06-19


Oh ok 😁

Naja bis Montag haha 🙄



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 903
Wohnort: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-06-21


Hallo Mauzi,

wie steht es mit der Aufgabe?

Ich würde ungefähr in dem Stil hier weitermachen wollen.

mfg
thureduehrsen



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]