www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Formale Sprachen" - Übergangsrelation
Übergangsrelation < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Übergangsrelation: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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



        
Bezug
Übergangsrelation: zur Turingmaschine
Status: (Antwort) fertig Status 
Datum: 11:28 So 06.09.2009
Autor: schachuzipus

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

Bezug
                
Bezug
Übergangsrelation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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


Bezug
                        
Bezug
Übergangsrelation: Antwort
Status: (Antwort) fertig Status 
Datum: 18:20 So 06.09.2009
Autor: schachuzipus

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]
>  
>
>
> > 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 [ok] 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  


Bezug
        
Bezug
Übergangsrelation: kurz zum Kellerautomaten
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:37 So 06.09.2009
Autor: schachuzipus

Hallo nochmal,

ich finde, der []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



Bezug
                
Bezug
Übergangsrelation: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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




Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de