Übergangsrelation < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 02:00 So 06.09.2009 | | Autor: | hasso |
Hallo,
ich tu mich bissien schwer Übergangsrelation vom kellerautomat und der Turing Maschine ganz abstrakt zu erklären. Und zwar hab ich in gegogelt um die bedeutung der einzelnen Zeichen herauszufinden.
Z - ist eine endliche Menge von zuständen
[mm] \times [/mm] - Kartesisches Produkt sprich die geordneten paare
ɼ soll das bandalphabet sein.
L steht für links und R steht für rechts
Sprich die Übergangsrelation von der TM ist:
[mm] \delta: [/mm] Z [mm] \times [/mm] ɼ -> Z [mm] \times [/mm] ɼ [mm] \times [/mm] {L,R}
Ich würd sagen das [mm] \times [/mm] {L,R} ist die Menge der möglichen Positionsänderungen der Köpfe, nämlich „links“, „rechts“ ist
vom Kellerautomaten:
[mm] \delta: [/mm] Z [mm] \times [/mm] ( E [mm] \cup [/mm] {epsilon}) [mm] \times [/mm] ɼ -> (Z [mm] \times [/mm] ɼ* )
lg hasso
|
|
| |
|
Hallo hasso,
mal zur TM:
Eine (deterministische) TM ist ein 7-Tupel [mm] $(Z,\Sigma,\Gamma,\delta,\Box,E)$ [/mm] mit:
[mm] $\bullet$ [/mm] einer Menge $Z$ von endlich vielen Zuständen und einem ausgezeichneten Zustand [mm] $z_0$, [/mm] dem Startzustand
[mm] $\bullet$ [/mm] einer Menge [mm] $E\subset [/mm] Z$ von Endzuständen
[mm] $\bullet$ [/mm] einem Eingabealphabet [mm] $\Sigma$ [/mm] (o.E. [mm] $\Sigma=\{0,1\}$)
[/mm]
[mm] $\bullet$ [/mm] einem Arbeitsalphabet [mm] $\Gamma$, [/mm] das neben den Zeichen des Eingabealphabetes noch einen blank [mm] $\Box$ [/mm] enthält
[mm] $\bullet$ [/mm] einer Überführungsfunktion [mm] $\delta:Z\times\Gamma\to Z\times\Gamma\times\{L,R,N\}$
[/mm]
genauer eigentlich [mm] $\delta:(Z\setminus E)\times\Gamma\to Z\times\Gamma\times\{L,R,N\}$, [/mm] denn wenn die TM in einem Endzustand ist, hält sie ja an, da wird nix mehr überführt.
Das (beidseitig unendliche) Band einer TM ist in Zellen eingeteilt, zu Beginn befindet sich eine Eingabe [mm] $x_1,x_2,...,x_n$ [/mm] auf dem Band [mm] $(x_i\in\{0,1\})$, [/mm] sonst nur blanks.
Der L/S-Kopf befindet sich über "Zelle 1", wo er [mm] $x_1$ [/mm] liest.
Die Übergangsfunktion lässt sich so erklären:
Nimm an, die TM ist nun in einem Zustand [mm] $z\in [/mm] Z$ (der kein Endzustand ist - siehe Bemerkung oben) und liest ein [mm] $x\in\Gamma$ [/mm] ein. Dann bewirkt die Übergangsfunktion [mm] $\delta$, [/mm] dass
1) die TM (bzw. ihr L/S-Kopf  ) das Zeichen $x$ mit einem Zeichen [mm] $x'\in\Gamma$, [/mm] also einer $0,1$ oder [mm] $\Box$ [/mm] überschreibt
2) die TM in einen neuen Zustand [mm] $z'\in [/mm] Z$ (möglicherweise ein Endzustand) übergeht oder im Zustand $z$ bleibt
3) der L/S-Kopf nach links (L), nach rechts (R) weitergeht oder stehenbleibt (N)
Ein Paar aus Zustand und eingelesenem Zeichen, also $(z,x)$ wird abgebildet auf ein Tripel aus Zustand, Zeichen und "Bewegung" $(z',x',b)$ [mm] ($b\in\{L,R,N\}$)
[/mm]
Also [mm] $\delta(z,x)=(z',x',b)$
[/mm]
Ich hoffe, nun ist klar, was das Tupel linkerhand und das Tripel rechterhand in der Definition von [mm] $\delta$ [/mm] bedeuten.
Noch ein Bsp.
Nehmen wir an, auf dem Band steht eine Zeichenfolge aus den Zeichen [mm] $0,1,\Box$ [/mm] und der L/S-Kopf befindet sich über dem Zeichen 1, die TM ist im Zustand $z$.
Was besagt dann der Übergang [mm] $\delta(z,1)=(z',0,N)$ [/mm] ?
Soweit erstmal zur TM, wenn du noch Fragen hast, nur zu ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:11 So 06.09.2009 | | Autor: | hasso |
Hallo schachuzipus,
Ich denke ich habs jetzt verstanden, hab mich schwer getan mit diesen komischen kreuz das kartesisches Produkt.
> mal zur TM:
>
> Eine (deterministische) TM ist ein 7-Tupel
> [mm](Z,\Sigma,\Gamma,\delta,\Box,E)[/mm] mit:
>
> [mm]\bullet[/mm] einer Menge [mm]Z[/mm] von endlich vielen Zuständen und
> einem ausgezeichneten Zustand [mm]z_0[/mm], dem Startzustand
>
> [mm]\bullet[/mm] einer Menge [mm]E\subset Z[/mm] von Endzuständen
>
> [mm]\bullet[/mm] einem Eingabealphabet [mm]\Sigma[/mm] (o.E. [mm]\Sigma=\{0,1\}[/mm])
>
> [mm]\bullet[/mm] einem Arbeitsalphabet [mm]\Gamma[/mm], das neben den Zeichen
> des Eingabealphabetes noch einen blank [mm]\Box[/mm] enthält
>
> [mm]\bullet[/mm] einer Überführungsfunktion
> [mm]\delta:Z\times\Gamma\to Z\times\Gamma\times\{L,R,N\}[/mm]
>
Also Übergangsrelation erläutert:
Die TM befindet sich in einen Zustand und liest einen Zeichen auf dem Bandalphabet(das beidseitig unendliche Band) dann übergeht Sie in den Folgezustand ersetzt das gelesene zeichen mit einen anderen Zeichen und macht dann je nachdem was in der Turing Tabelle steht dann eine "Links" "Rechts" "oder bleibt stehen" Bewegung.
> Noch ein Bsp.
>
> Nehmen wir an, auf dem Band steht eine Zeichenfolge aus den
> Zeichen [mm]0,1,\Box[/mm] und der L/S-Kopf befindet sich über dem
> Zeichen 1, die TM ist im Zustand [mm]z[/mm].
>
> Was besagt dann der Übergang [mm]\delta(z,1)=(z',0,N)[/mm] ?
Die TM befindet sichg in zustand z, liest mit dem Lesekopf auf dem Band eine 1 wechselt in den folge
Zustand z' überschreibt die 1 mit dem Lese-Schreibkopf mit einer 0 und hält an.
So richtig?
> Soweit erstmal zur TM, wenn du noch Fragen hast, nur zu
> ...
Vielen dank!
Liebe grüße
hasso
|
|
|
| |
|
Hey hasso,
> Hallo schachuzipus,
>
> Ich denke ich habs jetzt verstanden, hab mich schwer getan
> mit diesen komischen kreuz das kartesisches Produkt.
>
> > mal zur TM:
> >
> > Eine (deterministische) TM ist ein 7-Tupel
> > [mm](Z,\Sigma,\Gamma,\delta,\Box,E)[/mm] mit:
> >
> > [mm]\bullet[/mm] einer Menge [mm]Z[/mm] von endlich vielen Zuständen und
> > einem ausgezeichneten Zustand [mm]z_0[/mm], dem Startzustand
> >
> > [mm]\bullet[/mm] einer Menge [mm]E\subset Z[/mm] von Endzuständen
> >
> > [mm]\bullet[/mm] einem Eingabealphabet [mm]\Sigma[/mm] (o.E. [mm]\Sigma=\{0,1\}[/mm])
> >
> > [mm]\bullet[/mm] einem Arbeitsalphabet [mm]\Gamma[/mm], das neben den Zeichen
> > des Eingabealphabetes noch einen blank [mm]\Box[/mm] enthält
> >
> > [mm]\bullet[/mm] einer Überführungsfunktion
> > [mm]\delta:Z\times\Gamma\to Z\times\Gamma\times\{L,R,N\}[/mm]
> >
>
> Also Übergangsrelation erläutert:
>
> Die TM befindet sich in einen Zustand und liest einen
> Zeichen auf dem Bandalphabet(das beidseitig unendliche
> Band) dann übergeht Sie in den Folgezustand ersetzt das
> gelesene zeichen mit einen anderen Zeichen und macht dann
> je nachdem was in der Turing Tabelle steht dann eine
> "Links" "Rechts" "oder bleibt stehen" Bewegung. ![[ok]](/images/smileys/ok.gif "[ok]")
>
>
>
> > Noch ein Bsp.
> >
> > Nehmen wir an, auf dem Band steht eine Zeichenfolge aus den
> > Zeichen [mm]0,1,\Box[/mm] und der L/S-Kopf befindet sich über dem
> > Zeichen 1, die TM ist im Zustand [mm]z[/mm].
> >
> > Was besagt dann der Übergang [mm]\delta(z,1)=(z',0,N)[/mm] ?
>
> Die TM befindet sichg in zustand z, liest mit dem Lesekopf
> auf dem Band eine 1 wechselt in den folge
> Zustand z' überschreibt die 1 mit dem Lese-Schreibkopf
> mit einer 0 und hält an.
Jein, sie bleibt an derselben Stelle des Bandes stehen.
Wenn z' kein Endzustand ist, geht's aber weiter, nun müsste man in der Tabelle nachgucken, was die TM im Zustand z' macht, wenn sie eine 0 liest ...
>
> So richtig?
Fast ganz, die TM muss aber nicht zwingend halten, wenn der L/S-Kopf sich mal nicht bewegt, das hängt vom Zustand ab, in den die TM übergeht.
Von daher ist meine Bezeichnung für (N)=stehenbleiben nicht besonders glücklich gewesen. Es ist nicht im Sinne von "die TM hält" (wie in einem Endzustand) gemeint, sondern im Sinne von "der L/S-Kopf bewegt sich in diesem Übergangsschritt nicht.
>
> > Soweit erstmal zur TM, wenn du noch Fragen hast, nur zu
> > ...
> Vielen dank!
>
> Liebe grüße
> hasso
Ebenso
schachuzipus
|
|
|
| |
|
Hallo nochmal,
ich finde, der ![[]](/images/popup.gif) Artikel auf wikipedia erklärt den Kellerautomaten und die Übergangsrelation ganz gut.
Vllt. schaust du dir den mal an, falls du es noch nicht getan haben solltest
Das Prinzip der Übergangsrelation ist ja sehr ähnlich dem der TM, es fällt aber die Auswahl der "Bewegungen" (L,R,N) weg, beim KA wird die Bandeingabe step-by-step abgearbeitet.
Mit der Erklärung der ÜF der TM aus der anderen Antwort, kannst du dir vllt. die Funktionsweise der ÜR des KA selber klarmachen ...
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:59 So 06.09.2009 | | Autor: | hasso |
Hallo schachuzipus,
Die Übergangsrelation vom Kellerautomaten:
[mm]\delta:[/mm] Z [mm]\times[/mm] ( E [mm]\cup[/mm] {epsilon}) [mm]\times[/mm] ɼ -> (Z [mm]\times[/mm] ɼ* )
Wobei,
Z- eine endliche menge von Zuständen ist (z oder zi)
E - ein Alphabet, das so geannte Eingabealpbabet.
ɼ - Ist das kelleralpbaet der sogenannte Stack.
epsilon - Das leere Wort
Erläuterung der Übergangsralation meiner Meinung:
Man befindet sich in zustand Z es findet ein Eingabezeichen statt oder auch nicht je nach Eingabe befinden sich im keller folgendes zeichen.
Dann wechselt man in Zustand Z' und im Kelleralpbaet ist entweder Leer oder nicht Leer.
und?
lg hasso
|
|
|
|
