Turingmaschine (LBA) < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:57 Mo 15.11.2010 | | Autor: | Lovelace |
Ich befinde mich im Moment in der Prüfungsvorbereitung. Leider stehe ich in einigen Punkten gerade total auf dem Schlauch! Ich wäre daher sehr dankbar, wenn mir jemand ein bisschen auf die Sprünge helfen könnte...
1) Eine linear beschränkte Touringmaschine unterscheidet sich von einer allgemeinen, dass sie den Teil des Eingabebandes, auf dem die Eingabe steht niemals verlässt. Dazu muss sie ja Eingabeanfang und Eingabeende irgendwie "erkennen". Da der Schreib-Lesekopf am Anfang immer am Wortanfang steht, stellt das ja kein Problem dar. Man kann ja dann einfach die Stelle gleich im ersten Schritt markieren.
Allerdings verstehe ich nicht, wie die letzte Stelle des Eingabebandes erkannt wird...kann mir da jemand helfen?
In meinem Skript steht dazu etwas von "wir verdoppeln dazu Eingabealphabet [mm] \summe [/mm] zu [mm] \summe [/mm] ' = [mm] \summe \cup [/mm] {â| a [mm] \in \summe [/mm] }.
--> ist mir leider völlig unklar! wie soll das denn dann auch in meiner Automatenbeschreibung aussehen???
Vielen vielen Dank für die Hilfe!
Viele Grüße
Lovelace
P.S.: ich habe die Frage in keinem anderen Forum gepostet!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:59 Di 16.11.2010 | | Autor: | felixf |
Moin Ada!
> Ich befinde mich im Moment in der Prüfungsvorbereitung.
> Leider stehe ich in einigen Punkten gerade total auf dem
> Schlauch! Ich wäre daher sehr dankbar, wenn mir jemand ein
> bisschen auf die Sprünge helfen könnte...
>
> 1) Eine linear beschränkte Touringmaschine unterscheidet
Du meinst eine Turingmaschine. Da wird nix getourt 
> sich von einer allgemeinen, dass sie den Teil des
> Eingabebandes, auf dem die Eingabe steht niemals verlässt.
> Dazu muss sie ja Eingabeanfang und Eingabeende irgendwie
> "erkennen". Da der Schreib-Lesekopf am Anfang immer am
> Wortanfang steht, stellt das ja kein Problem dar. Man kann
> ja dann einfach die Stelle gleich im ersten Schritt
> markieren.
> Allerdings verstehe ich nicht, wie die letzte Stelle des
> Eingabebandes erkannt wird...kann mir da jemand helfen?
> In meinem Skript steht dazu etwas von "wir verdoppeln dazu
> Eingabealphabet [mm]\summe[/mm] zu [mm]\summe[/mm] ' = [mm]\summe \cup[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{â| a [mm]\in \summe[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> }.
> --> ist mir leider völlig unklar! wie soll das denn dann
> auch in meiner Automatenbeschreibung aussehen???
Nun, man koennte z.B. sagen, dass die Eingabe das letzte Zeichen mit Hut haben soll, und alle davor nicht. Aus der Eingabe $123984213$ wird z.B. $12398421\hat{3}$.
Dann kannst du die Turing-Maschine so aendern, dass sie das Huetchen ignoriert, es sei denn sie will nach rechts gehen, dann darf sie das halt nicht wenn da ein Huetchen an der aktuellen Stelle ist.
Man kann das auch anders machen, wie etwa ![[]](/images/popup.gif) hier, indem man zwei spezielle Symbole ins Alphabet aufnimmt (linker und rechter Endmarker) und bei der Eingabe halt immer vorne den linken Endmarker und hinten den rechten Endmarker anhaengt.
Damit aendert sich das Format der Eingabe, aber halt nur minim.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:44 Di 16.11.2010 | | Autor: | Lovelace |
| Aufgabe | | Zeigen Sie durch Angabe eines LBA, dass die Sprache B= [mm] (a^{i}ba^{i}) [/mm] kontextsensitiv ist. |
Hallo Felix!
Vielen Dank für deine Antwort erst einmal! Ich würde das jetzt einfach mal an einem Beispiel probieren: Mein LBA könnte ja dann folgendermaßen aussehen:
M= ( (a, b, â, ^b) , (a, b, â, ^b, A), [mm] (z_{0}, ...z_{e}), \delta, z_{0}z_{e},)
[/mm]
-->ist das so richtig??? Und dann baue ich TM so, dass sie dieses erste â und das letzte â immer lässt und ansonsten die a´s vorne und hinten jeweils paarweise durch A ersetzt. wenn das dann funktioniert und am Ende die komplette Eingabe nur aus As, einem b und â an Eingabeanfang und Eingabeende steht, dann gehe ich in den Endzustand über... vom Prinzip her richtig???
Vielen dank,
liebe Grüße,
Ada
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:19 Di 16.11.2010 | | Autor: | felixf |
Moin!
> Zeigen Sie durch Angabe eines LBA, dass die Sprache B=
> [mm](a^{i}ba^{i})[/mm] kontextsensitiv ist.
> Hallo Felix!
>
> Vielen Dank für deine Antwort erst einmal! Ich würde das
> jetzt einfach mal an einem Beispiel probieren: Mein LBA
> könnte ja dann folgendermaßen aussehen:
>
> M= ( (a, b, â, ^b) , (a, b, â, ^b, A), [mm](z_{0}, ...z_{e}), \delta, z_{0}z_{e},)[/mm]
Je nachdem was so ein Tupel bei euch bedeutet, vermutlich ja.
> -->ist das so richtig??? Und dann baue ich TM so, dass sie
> dieses erste â und das letzte â immer lässt und
> ansonsten die a´s vorne und hinten jeweils paarweise durch
> A ersetzt. wenn das dann funktioniert und am Ende die
> komplette Eingabe nur aus As, einem b und â an
> Eingabeanfang und Eingabeende steht, dann gehe ich in den
> Endzustand über... vom Prinzip her richtig???
Ja.
Die akzeptierte Sprache ist jetzt natuerlich [mm] (a^i [/mm] b [mm] a^{i-1} \hat{a}), [/mm] wobei fuer $i = 0$ da [mm] $\hat{b}$ [/mm] stehen sollte. (Falls $i = 0$ zulaessig ist, musst du den Algorithmus auch noch entsprechend anpassen.)
LG Felix
|
|
|
|
