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" - Turing Maschine
Turing Maschine < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Turing Maschine: MTM frage
Status: (Frage) beantwortet Status 
Datum: 20:04 Di 10.02.2009
Autor: Yas

Hallo zusammen, ich brauche hilfe mit diese frage !

Sei L = {w $ [mm] w^R [/mm] | w{a, b}*}, wobei [mm] w^R [/mm] das rückwärts notierte Wort w ist.

1. Geben Sie eine deterministische 1-Band TM [mm]M_1 [/mm]  an, die L akzeptiert und auf allen Eingaben hält.

2. Geben Sie die Anzahl der von [mm]M1[/mm] ausgeführten Schritte in Abhängigkeit der Eingabelänge an.

so meine frage ist wie kann ich die ergebniss speichern? Ich fange von der erste simbol auf dem band, dann gehe ich Rechts bis ich Dollar sign finde danach wie kann ich speichern die symbole, die nach die Dollar sign kommt???
kann mir jemand hilfen??

Danke!

        
Bezug
Turing Maschine: Antwort
Status: (Antwort) fertig Status 
Datum: 08:42 Do 12.02.2009
Autor: bazzzty


> Hallo zusammen, ich brauche hilfe mit diese frage !
>  
> Sei [mm]L = \{w \$ w^R | w\in\{a, b\}^\star\}[/mm], wobei [mm]w^R[/mm] das rückwärts
> notierte Wort w ist.
>  
> 1. Geben Sie eine deterministische 1-Band TM [mm]M_1[/mm]  an, die L
> akzeptiert und auf allen Eingaben hält.
>  
> 2. Geben Sie die Anzahl der von [mm]M1[/mm] ausgeführten Schritte in
> Abhängigkeit der Eingabelänge an.
>  
> so meine frage ist wie kann ich die ergebniss speichern?

Das "Ergebnis" bei einer Turing-Maschine ist im Zustand kodiert, in dem die Maschine anhält. Es gibt Finalzustände (in denen die Maschine hält) und darunter akzeptierende, d.h. "JA"-Finalzustände, und nicht-akzeptierende "NEIN"-Zustände. Mehr gibt es nicht zu speichern.

> Ich fange von der erste simbol auf dem band, dann gehe ich
> Rechts bis ich Dollar sign finde danach wie kann ich
> speichern die symbole, die nach die Dollar sign kommt???
> kann mir jemand hilfen??

Tja, so eine Turing-Maschine ist nicht so einfach. Man kann sich nicht viel "merken". Es wird auch nicht reichen, einmal über den ersten und einmal über den zweiten Teil zu laufen. Ich kann Dir aber mal eine mögliche Lösung (es gibt viele!) erklären, und Du versuchst das in einer Turing-Maschine zu kodieren:

1. Gehe vor bis zum (ersten) Dollarzeichen.
2. Lies das Zeichen davor, merke es Dir und überschreibe mit einem Dollarzeichen.
3. Gehe bis zum letzten Dollarzeichen.
4. Lies das Zeichen, vergleiche mit dem gemerkten, überschreibe mit einem Dollarzeichen. Ist es ungleich, halte nichtakzeptierend. Sonst gehe zurück zum ersten Dollarzeichen und mache bei "2." weiter.

Was fehlt noch zum Akzeptieren? Welcher Schritt muss verändert werden?

Kannst Du eine solche Turing-Maschine beschreiben?



Bezug
                
Bezug
Turing Maschine: ja aber
Status: (Frage) überfällig Status 
Datum: 10:39 Do 12.02.2009
Autor: Yas


>  2. Lies das Zeichen davor, merke es Dir und überschreibe
> mit einem Dollarzeichen.

genau das moechte ich wissen wenn ich jetzt zum bsp. ein "a" gelesen habe wie kann ich dieses "a" merken? brauche ich stack?

> Was fehlt noch zum Akzeptieren? Welcher Schritt muss
> verändert werden?

wie meinst du?


> Kannst Du eine solche Turing-Maschine beschreiben?

normale weise schon :P

>  

danke!

Bezug
                        
Bezug
Turing Maschine: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:25 Do 12.02.2009
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                
Bezug
Turing Maschine: sorry
Status: (Frage) überfällig Status 
Datum: 11:19 Do 12.02.2009
Autor: Yas

Ich bin sooo doof (sorry) das ist doch einfach zu bemerken ob ein a oder b gelesen worden, durch schritte!!! Also schritt [mm] S_a [/mm] bzw. [mm] S_b [/mm] wenn ich ein a bzw. b gelesen habe.
> Was fehlt noch zum Akzeptieren? Welcher Schritt muss
> verändert werden?

das habe ich nicht verstanden! was meinst du da mit?kannst du vielleicht erklehren?
  
danke!

Bezug
                        
Bezug
Turing Maschine: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:25 Do 12.02.2009
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                
Bezug
Turing Maschine: hilfeee
Status: (Frage) überfällig Status 
Datum: 13:43 Do 12.02.2009
Autor: Yas


> Was fehlt noch zum Akzeptieren? Welcher Schritt muss
> verändert werden?

Was heisst das?
  

> Kannst Du eine solche Turing-Maschine beschreiben?

Ja habe ich, ist das richtig?

  $=d
           a        b                      d                               Blanck
S0     S0,a,R    S0,b,R                 S1,d,L                       Sl,blanck,R
S1     Sa,d,R    Sb,d,R                 S1,d,L                       Ja,blanck,N
Sa     S1,d,L    Nein,b,N              Sa,d,R                       ------
Sb     Nein,a,N  S1,d,L                 Sb,d,R                      ---------
Sl      Nein,a,N   Nein,b,N             Sl,dollar,R                Ja,blanck,N


2. teil des Frage ist mir jetzt wichtig!!!

Danke!


Bezug
                        
Bezug
Turing Maschine: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:20 Do 12.02.2009
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de