Entscheidbarkeit reg. Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:46 Di 06.06.2006 | | Autor: | dobberph |
| Aufgabe | | Zeigen Sie formal, dass reguläre Sprachen entscheidbar sind. |
Hi ihr,
ich hab bei dieser Frage ein wenig Bauchschmerzen, da
der Professor wirklich absolut formale Beweise sehen will und einiges hier aus dem Forum ihm nicht genug war... ;D
Verwendbare Sätze:
a.) Entscheidbare Sprache:
Es ex. eine Touringmaschine, die für jedes Wort hält und angibt, ob das Wort [mm] \in [/mm] oder [mm] \not\in [/mm] der Sprache L ist.
b.) reguläre Sprache:
zu jeder regulären Sprache gibt es einen nea/dea.
Ansatz:
Ich soll also vermutlich zeigen, dass ich zu jeder Touringmaschine TM, für die a.) gilt einen nea/dea konstruieren kann, damit b.) gilt.
Aber wie macht man das formal???????
Mfg,
DerTobi
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt
|
|
| |
|
Hallo Tobi,
es heisst Turing-Maschine , benannt nach A. Turing, und nicht ''Touring-Maschine'' !!!
Nun, es handelt sich doch um eine einfache Pfadsuche in einem gerichteten Graphen, nicht wahr ? ZB. Tiefensuche oder Breitensuche tun es
(bei NEA, wenn Du über DEA gehst, ist es eine einfache Simulation.
Das ist nicht der Beweis formal ausgearbeitet, aber in Essenz der Grund für die Richtigkeit der zu beweisenden Aussage.
Formal musst Du in der Tat zeigen, dass es zu jedem [mm] A\in [/mm] REG eine TM [mm] M_A [/mm] gibt mit [mm] L(M_A)=L. [/mm]
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:55 Di 06.06.2006 | | Autor: | dobberph |
Äh, ja klar,
aber meine Frage ist, wie man sowas formal zeigt.
Klar, eine Vorschrift für die Konstruktion eines DEA/NEA geht über Pfadsuche, aber das ist nicht formal (nicht mal ein Beweis).
Man müsste danach noch zeigen, dass man diese Konstruktion immer anwenden kann und dass es keine Spezialfälle gibt usw.
Das sollen wir aber nicht tun glaube ich. Sonst würde er nicht so explizit formal hinschreiben...
Mfg,
DerTobi
|
|
|
| |
|
Hallo Tobi,
ok, betrachte also eine reg. Sprache L, dann gibt es einen deterministischen endlichen Automaten A mit L(A)=L.
Konstruiere nun einfach eine TM M, die essentiell nichts anderes tut als A: sie benutzt nur das Eingabeband, liest in jedem Schritt ein Zeichen,
verändert dies nicht, geht wie A in den entspr. Nachfolgezustand und bewegt den Kopf um ein Feld nach rechts -
um es formaler zu machen, müsst man Eure Notation von TM's und DEA im Detail berücksichtigen.
Ich denke, so kommst Du aber schon weiter, oder ?
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:22 Di 06.06.2006 | | Autor: | dobberph |
Hm, nein leider nicht.
So rum würde ich es irgendwie noch selbst hinkriegen...
Mein Tutor meinte, dass wir es genau anders herum zeigen müssen:
dass es zu einer beliebige Turingmaschine TM einen nea M gibt, der das gleiche tut und L(M) akzeptiert, so dass TM [mm] \equiv [/mm] M .
Mfg,
DerTobi
|
|
|
| |
|
Hallo Tobi,
es gibt halt überall auch ein gewisses Spektrum hinsichtlich Kompetenz und Qualität - jedenfalls
sind die regulären Sprachen eine echte Teilmenge der Turing-entscheidbaren Sprachen, und zum Nachweis dieses
Sachverhaltes muss man also zu einer reg. Sprache L=L(A), A ein DEA (oder NEA) eine TM konstruieren.
Gruss,
Mathias
|
|
|
|
