Turingmaschine < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:52 Fr 24.05.2013 | | Autor: | bandchef |
| Aufgabe | Hier die Aufgabe: http://s14.directupload.net/file/d/3265/ubh2xc8w_png.htm
Heute mal in Bildform, weil der LaTeX-Code recht umfangreich geworden wäre! |
Hi Leute!
Ich hab im ersten Schritt versucht, die Turingmaschine textuell zu erklären. Leider hat mir das aber noch nicht so viel geholfen, zu erkennen, welche Sprache die Maschine erkennt. Dann hab ich versucht, die textuelle Erklärung in einen DEA zu packen; hat auch nur bis Zustand [mm] $q_2$ [/mm] der Übergangstabelle geklappt. Ab jetzt bin ich ratlos...
q0: eine 0 lesen, dann in q1 schalten
q1: solange 0en lesen bis 1 kommt, dann in q1 schalten
q2: solange 1en lesen bis # kommt, dann in q3 schalten
q3: wenn 1, dann 1 mit # ersetzen, dann in q4 schalten
q4: solange # lesen bis 0 oder 1 kommt, dann in q5 schalten ODER solange 0en lesen bis #oder 1 kommt, dann in q5 oder q4 schalten ODER 1en lesen bis # oder 0 kommt, dann in q5 oder q4 schalten
q5: solange # lesen bis 0 oder 1 kommt, dann in q6 oder q8 schalten ODER wenn 0, dann 0 mit # ersetzen dann in q6 schalten ODER solange 1en lesen, bis # oder 0 kommt, dann in q8 oder q6 schalten
q6: solange # lesen bis 0 oder 1 kommt, dann in q8 schalten ODER solange 0en lesen bis # oder 1 kommt, dann in q7 schalten ODER solange 1en lesen bis # oder 0 kommt, dann in q7 schalten
q7: solange # lesen bis 0 oder 1 kommt, dann in q7 schalten ODER solange 0en lesen bis # oder 1 kommt, dann in q3 oder q7 schalten ODER solange 1en lesen bis # oder 0 kommt, dann in q3 oder q7 schalten
Ich hoffe die Übersetzung stimmt soweit. Ab q2 funktioniert auch das erstellen eines DEAs nicht mehr, weil ich dann Probleme mit dem dritten Zeichen, dem #, bekomme.
Ich hoffe ihr könnt mir helfen!
Danke!
|
|
| |
|
Hallo bandchef,
> q0: eine 0 lesen, dann in q1 schalten
Hiermit hast Du schon den ersten Anhaltspunkt, denn was heißt das für die gesuchte Sprache? Konkret: Für den Beginn der Sprache? Könnte man die Sprache hierdurch vielleicht schon einschränken? 
> q1: solange 0en lesen bis 1 kommt, dann in q1 schalten
>
> q2: solange 1en lesen bis # kommt, dann in q3 schalten
Genau, da nimmt doch die gesuchte Sprache schon ein wenig Gestalt an, oder? Versuch Dir das einfach mal zu verdeutlichen. Du hast demnach bisher
eine Reihe von Nullen gefolgt von Einsen.
> q3: wenn 1, dann 1 mit # ersetzen, dann in q4 schalten
Was heißt "wenn"? Kann es sein, dass Dir die Bedeutung von L und R nicht klar ist?
>
> q4: solange # lesen bis 0 oder 1 kommt, dann in q5 schalten
> ODER solange 0en lesen bis #oder 1 kommt, dann in q5 oder
> q4 schalten ODER 1en lesen bis # oder 0 kommt, dann in q5
> oder q4 schalten
Wieso denn "Solange # lesen bis 0 oder 1 kommt"? Ich glaube, dass Du
da generell etwas noch nicht so richtig verstanden hast.
-> Wenn #, dann in Zustand [mm] q_5 [/mm] wechseln
-> "Solange 0en lesen bis" heißt für Dich was? Wie bewegt sich der Lesekopf dabei?
Und was genau heißt für Dich "ODER" - wie stellst Du Dir das bildlich vor mit der Turingmaschine und dem Lesen.
Es ist hier so, dass er hier solange Nullen und Einsen liest, bis er auf # trifft -
wo befindet sich der Lesekopf dann?
BTW Du weißt was # genau ist?
>
> q5: solange # lesen bis 0 oder 1 kommt, dann in q6 oder q8
> schalten ODER wenn 0, dann 0 mit # ersetzen dann in q6
> schalten ODER solange 1en lesen, bis # oder 0 kommt, dann
> in q8 oder q6 schalten
.. nein. Kein solange. Der Lesekopf liest das Zeichen. Das ist entweder 0 oder 1 oder #. Ist es eine 0, dann diese mit # ersetzen (richtig erkannt von Dir) und zu [mm] q_6.
[/mm]
Ist es 1 oder #, dann wechselt er zu [mm] q_8 [/mm] . BTW was bedeutet / ist [mm] q_8, [/mm] weißt Du das? Und was bedeutet es, dass er dahin schaltet für das gesuchte Wort?
...
Ich habe den Rest Deiner "Übersetzung" jetzt mal nicht weiter kommentiert.
Ich würde mir an Deiner Stelle einfach mal das plastisch vorstellen.
Also Du hast ein Band mit Feldern, jedes hat genau ein Zeichen (entweder 0,1 oder #) und es gibt den Schreib-/Lesekopf, der über einem Feld ist und dessen Zeichen liest bzw. darauf schreibt und sich von Feld zu Feld bewegt.
Bei Deiner "Übersetzung" bist Du nie auf L/R eingegangen. Du bekommst eine recht klare Vorstellung von der akzeptierten Sprache, wenn Du das mal so "gedanklich durchsimulierst".
Gruß
Anna
|
|
|
| |
|
Hallo bandchef,
> q0: eine 0 lesen, dann in q1 schalten
Hiermit hast Du schon den ersten Anhaltspunkt, denn was heißt das für die gesuchte Sprache? Konkret: Für den Beginn der Sprache? Könnte man die Sprache hierdurch vielleicht schon einschränken?
> q1: solange 0en lesen bis 1 kommt, dann in q1 schalten
>
> q2: solange 1en lesen bis # kommt, dann in q3 schalten
Genau, da nimmt doch die gesuchte Sprache schon ein wenig Gestalt an, oder? Versuch Dir das einfach mal zu verdeutlichen. Du hast demnach bisher
eine Reihe von Nullen gefolgt von Einsen.
> q3: wenn 1, dann 1 mit # ersetzen, dann in q4 schalten
Was heißt "wenn"? Kann es sein, dass Dir die Bedeutung von L und R nicht klar ist?
>
> q4: solange # lesen bis 0 oder 1 kommt, dann in q5 schalten
> ODER solange 0en lesen bis #oder 1 kommt, dann in q5 oder
> q4 schalten ODER 1en lesen bis # oder 0 kommt, dann in q5
> oder q4 schalten
Wieso denn "Solange # lesen bis 0 oder 1 kommt"? Ich glaube, dass Du
da generell etwas noch nicht so richtig verstanden hast.
-> Wenn #, dann in Zustand [mm] q_5 [/mm] wechseln
-> "Solange 0en lesen bis" heißt für Dich was? Wie bewegt sich der Lesekopf dabei?
Und was genau heißt für Dich "ODER" - wie stellst Du Dir das bildlich vor mit der Turingmaschine und dem Lesen.
Es ist hier so, dass er hier solange Nullen und Einsen liest, bis er auf # trifft -
wo befindet sich der Lesekopf dann?
BTW Du weißt was # genau ist?
>
> q5: solange # lesen bis 0 oder 1 kommt, dann in q6 oder q8
> schalten ODER wenn 0, dann 0 mit # ersetzen dann in q6
> schalten ODER solange 1en lesen, bis # oder 0 kommt, dann
> in q8 oder q6 schalten
.. nein. Kein solange. Der Lesekopf liest das Zeichen. Das ist entweder 0 oder 1 oder #. Ist es eine 0, dann diese mit # ersetzen (richtig erkannt von Dir) und zu [mm] q_6.
[/mm]
Ist es 1 oder #, dann wechselt er zu [mm] q_8 [/mm] . BTW was bedeutet / ist [mm] q_8, [/mm] weißt Du das? Und was bedeutet es, dass er dahin schaltet für das gesuchte Wort?
...
Ich habe den Rest Deiner "Übersetzung" jetzt mal nicht weiter kommentiert.
Ich würde mir an Deiner Stelle einfach mal das plastisch vorstellen.
Also Du hast ein Band mit Feldern, jedes hat genau ein Zeichen (entweder 0,1 oder #) und es gibt den Schreib-/Lesekopf, der über einem Feld ist und dessen Zeichen liest bzw. darauf schreibt und sich von Feld zu Feld bewegt.
Bei Deiner "Übersetzung" bist Du nie auf L/R eingegangen. Du bekommst eine recht klare Vorstellung von der akzeptierten Sprache, wenn Du das mal so "gedanklich durchsimulierst".
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:07 Sa 25.05.2013 | | Autor: | bandchef |
> Hiermit hast Du schon den ersten Anhaltspunkt, denn was heißt das für die gesuchte Sprache? Konkret: Für den Beginn der Sprache? Könnte man die Sprache hierdurch vielleicht schon einschränken?
Es muss eine 0 am Anfang kommen, bevor überhaupt irgendwas gemacht wird.
> Was heißt "wenn"? Kann es sein, dass Dir die Bedeutung von L und R nicht klar ist?
Irgendwie glaub ich hab ich an dieser Stelle das Problem, dass ich nicht weiß, wie ich mit den zwei TM-Zuständen, als (q3,#,L) und (q2,1,R), umgehen muss. Die TM macht ja im Zustand q2 nur überhaupt was, wenn entweder ein # kommt, oder eine 1 kommt. Daher das "wenn"...
> Wieso denn "Solange # lesen bis 0 oder 1 kommt"? Ich glaube, dass Du da generell etwas noch nicht so richtig verstanden hast.
"Solange" deswegen weil ja die TM solange nach links weiter geht, so lange sie # liest. Sie liest ein # ersetzt es mit # wechselt den Zustand und geht einen Schritt weiter. So interpretiere ich diesen Übergang [mm] $(q_2, [/mm] #) [mm] \to [/mm] (q3,#,L)$ um den es sich doch hier gerade dreht, oder?
> Und was genau heißt für Dich "ODER" - wie stellst Du Dir das bildlich vor mit der Turingmaschine und dem Lesen.
Oder wenn eben 0en oder 1en kommen...
> Es ist hier so, dass er hier solange Nullen und Einsen liest, bis er auf # trifft - wo befindet sich der Lesekopf dann?
Wenn der Lesekopf auf ein # trifft, ist der Lesekopf am "Ende" des Bandes angelangt (das Band ist ja grundsätzlich mal unendlich lang, aber das Ende der Zeichen am Band wird damit simuliert).
> BTW Du weißt was # genau ist?
Das Limitierungszeichen. Hab ich ja weiter oben schon genauer erklärt.
> BTW was bedeutet / ist [mm] q_8, [/mm] weißt Du das? Und was bedeutet es, dass er dahin schaltet für das gesuchte Wort?
Meinst du mit "/" die Zeichen "-" im leeren Zustand q8? Wenn ja, dann bedeutet, dass die TM fertig ist, wenn sie in den Zustand q8 schalten darf. Der deterministische Zustand quasi, denn es handelt sich hier ja um eine deterministische TM.
> Bei Deiner "Übersetzung" bist Du nie auf L/R eingegangen. Du bekommst eine recht klare Vorstellung von der akzeptierten Sprache, wenn Du das mal so "gedanklich durchsimulierst".
Ok. Werde ich jetzt gleich nochmal probieren. Aber. Wenn ich nun ganz vorne in der Übergangstabelle anfange, dann und ich im Zustand q0 bin, und ich das dortige Zeichen lesen will, weiß ich ja nicht welches Zeichen sich dort verbirgt?!?!? Was soll ich dann lesen? Gut, hier ist das jetzt kein Problem, weil die TM sowieso nur mit einer 0 überhaupt irgendwas macht. Was müsste ich aber machen, wenn nun alle Felder (wie in q4, q5, q6, q7) ausgefüllt wären?
Ich hab hier nochmal versucht die Übergangstabelle zu interpretieren:
q0,q1,q2: eine feste 0, gefolgt von einer Reihe von beliebiger Anzehl 0en und 1en, bis ein # kommt, dann in q3 schalten
q3: die letzte 1 (auf der rechten Seite) löschen (durch # ersetzen) dann nach links gehen und in q4 schalten
q4: eine Reihe beliebig vieler 0en und 1en lesen und jeweils links gehen bis # gelesen wird, dann nach rechts gehen und in q5 schalten
q5: ein # akzeptieren (in q8 schalten) und rechts gehen, eine 1 akzeptieren und links gehen, eine 0 mit # ersetzen (löschen) nach rechts gehen und in q6 wechseln
q6: ein # akzeptieren (in q8 schalten) und rechts gehen, 0 oder 1 jeweils rechts gehen und in q7 schalten
q7: eine Reihe beliebiger Anzahl 0en und 1en lesen und jeweils rechts gehen, # lesen dann links gehen und in q3 schalten
Die Übergänge von q0 bis q4 kann ich jetzt eigentlich schon gut interpretieren: Es muss eine feste 0 gefolgt von einer beliebigen Anzahl 0en und 1en. Wenn am Ende angekommen, dann letzte 1 löschen und dann wieder beliebig viele 0en und 1en lesen bis man beim linken # angekommen ist.
Weiter verstehe ich das ganze leider nicht :-(
Kannst du mir an dieser Stelle weiterhelfen?
|
|
|
| |
|
Hallo bandchef,
> > Hiermit hast Du schon den ersten Anhaltspunkt, denn was
> heißt das für die gesuchte Sprache? Konkret: Für den
> Beginn der Sprache? Könnte man die Sprache hierdurch
> vielleicht schon einschränken?
>
> Es muss eine 0 am Anfang kommen, bevor überhaupt irgendwas
> gemacht wird.
Konkreter: Falls nicht 0, wäre schon ein ungültiger Zustand das Resultat
Wir merken uns:
Die von M erkannte Sprache muss mit einer 0 beginnen.
> Irgendwie glaub ich hab ich an dieser Stelle das Problem,
> dass ich nicht weiß, wie ich mit den zwei TM-Zuständen,
> als (q3,#,L) und (q2,1,R), umgehen muss.
[mm] (q_3,#,L) [/mm] und [mm] (q_2,1,R) [/mm] sind ja keine Zustände, sondern das sind die Überführungsfunktionen im betreffenden Zustand [mm] q_2 [/mm] für das jeweils gelesene Zeichen (# bzw. 1)
> Ok. Werde ich jetzt gleich nochmal probieren. Aber. Wenn
> ich nun ganz vorne in der Übergangstabelle anfange, dann
> und ich im Zustand q0 bin, und ich das dortige Zeichen
> lesen will, weiß ich ja nicht welches Zeichen sich dort
> verbirgt?!?!? Was soll ich dann lesen? Gut, hier ist das
> jetzt kein Problem, weil die TM sowieso nur mit einer 0
> überhaupt irgendwas macht. Was müsste ich aber machen,
> wenn nun alle Felder (wie in q4, q5, q6, q7) ausgefüllt
> wären?
Ähm, ich gehe davon aus, dass hier eine 1-Band-DTM gemeint ist. Von daher geht es immer nur um 1 Feld pro Lesevorgang. In den Zuständen [mm] q_4,q_5,q_6,q_7 [/mm] macht die Maschine also immer was, egal welches Zeichen auf dem Feld ist.
> Die Übergänge von q0 bis q4 kann ich jetzt eigentlich
> schon gut interpretieren: Es muss eine feste 0 gefolgt von
> einer beliebigen Anzahl 0en und 1en. Wenn am Ende
> angekommen, dann letzte 1 löschen und dann wieder beliebig
> viele 0en und 1en lesen bis man beim linken # angekommen
> ist.
![[ok]](/images/smileys/ok.gif "[ok]") Genau. Damit steht der Schreib-/Lesekopf wieder vor dem Wort der akzeptierten Sprache.
> Weiter verstehe ich das ganze leider nicht :-(
>
> Kannst du mir an dieser Stelle weiterhelfen?
Wir sind also jetzt im Zustand [mm] q_5 [/mm] und betrachten das erste Zeichen des Wortes. Ist das ein # oder 1, dann geht die Maschine in den akzeptierten Endzustand [mm] q_8. [/mm] (BTW ist Dir klar, warum dazu die Maschine bei # nach rechts geht und bei einer 1 nach links?).
Was bedeutet es für unsere gesuchte Sprache, wenn in diesen Fällen die Maschine in den Endzustand geht? Tipp: Wir wissen ja bisher, dass sie aus einer beginnenden Null gefolgt von einer Reihe von Nullen und Einsen bestehen muss. Jetzt solltest Du schauen, ob die Anzahl oder das Verhältnis vielleicht noch irgendwie eine Rolle spielt ;)
Bei einer 0 wird diese, wie Du richtig erkannt hast, mit dem Blanksymbol überschrieben und es geht in den Zustand [mm] q_6, [/mm] im Grunde beginnt hier dann genau der oben beschriebene Prozess erneut. Versuch Dir das mal selbst klar zu machen. Du hast ein Band mit Feldern beschrieben mit Nullen und Einsen und dann simulier mal die Schritte nach.
Z.B. für #|0|0|0|1|1|1|1|#
oder für #|0|0|0|1|1|#
Würden beide akzeptiert werden?
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:09 So 26.05.2013 | | Autor: | bandchef |
> Ähm, ich gehe davon aus, dass hier eine 1-Band-DTM gemeint ist. Von daher geht es immer nur um 1 Feld pro Lesevorgang. In den Zuständen [mm] q_4,q_5,q_6,q_7 [/mm] macht die Maschine also immer was, egal welches Zeichen auf dem Feld ist.
Ja, es handelt sich auch in der Vorlesung um eine 1-Band-DTM.
> (BTW ist Dir klar, warum dazu die Maschine bei # nach rechts geht und bei einer 1 nach links?).
Wenn # gelesen wird, weiß die Maschine, dass sie sich am rechten Ende des Bandes befindet und es bleibt akzeptierend. Wenn eine 1 kommen würde weiß die Maschine, dass es das Wort ist und sie geht links und akzeptiert. Warum sie in diesen beiden Fällen aber akzeptiert verstehe ich nicht.
> Was bedeutet es für unsere gesuchte Sprache, wenn in diesen Fällen die Maschine in den Endzustand geht?
Dann erkennt die DTM das Wort und ich könnte daraus die Sprache ableiten?!?!?
> Tipp: Wir wissen ja bisher, dass sie aus einer beginnenden Null gefolgt von einer Reihe von Nullen und Einsen bestehen muss. Jetzt solltest Du schauen, ob die Anzahl oder das Verhältnis vielleicht noch irgendwie eine Rolle spielt ;)
Ich könnte mir vorstellen, dass die Maschine Wörter erkennt, die dem folgenden Aufbau ähneln: 000111, 00001111. Quasi gleiche Anzahl.
Ich hab nun auch durchsimuliert. Ich kapier's aber nicht so ganz.
Das Wort #0001111# wird bis zum Zustand q4 zu #000111##. Dann steht irgendwann der Lesekopf auf dem rechten #. Laut Übergangsfunktion (q5,#,R) bei Zustand q4 steht wechselt dann der Lesekopf auf die erste linke 0 und ich muss dann in den Zustand q5 gucken damit ich weiß wie es weiter geht. In Zustand q5 wird das Wort dann zu ##00111## und der Lesekopf geht nach rechts weiter und Zustandswechsel zu q6. Dann liest sie die zweite linke Null; das geht dann so weiter bis in Zustand q6 der Lesekopf das erste rechte # liest, dann wechselt sie von q6 in q8 und akzeptiert.
Das heißt wiederum, dass das Wort 0001111 von DTM akzeptiert wird. Stimmt so?
Das Wort 00011 wird von der DTM nicht akzeptiert, weil die DTM beim Zustandsübergang [mm] $(q_3,1) \to (q_4, \#, [/mm] L)$ nur noch links geht und wegen dem unendlichen Band, dass nach links wie rechts mit # beschrieben ist, liest die DTM unendlich lange # und kann so nie mehr akzeptieren...
Ich denke, dass die Sprache wohl so aussehen sollte: [mm] $L=\{0^n 1^{n+1} | n \in \mathbb N\}$. [/mm] Die Anzahl der 0en, die vor den 1en kommen, muss um eins kleiner sein als die Anzahl der 1en. Richtig?
|
|
|
| |
|
Hallo bandchef,
> > (BTW ist Dir klar, warum dazu die Maschine bei # nach
> rechts geht und bei einer 1 nach links?).
>
> Wenn # gelesen wird, weiß die Maschine, dass sie sich am
> rechten Ende des Bandes befindet und es bleibt
> akzeptierend. Wenn eine 1 kommen würde weiß die Maschine,
> dass es das Wort ist und sie geht links und akzeptiert.
> Warum sie in diesen beiden Fällen aber akzeptiert verstehe
> ich nicht.
Weil beides dann ein Wort der von uns gesuchten = akzeptierten Sprache ist. Und wenn Du Dir nun noch überlegst, warum manchmal schon am Anfang des "Restwortes" das gesamte Wort als zur akzeptierten Sprache zugehörig erkannt wird und manchmal erst ganz am Ende, dann bist Du der Lösung bzgl. des Verhältnis 0 zu 1 schon sehr nahe.
>
>
>
> > Was bedeutet es für unsere gesuchte Sprache, wenn in
> diesen Fällen die Maschine in den Endzustand geht?
>
> Dann erkennt die DTM das Wort und ich könnte daraus die
> Sprache ableiten?!?!?
Genau.
> Das heißt wiederum, dass das Wort 0001111 von DTM
> akzeptiert wird. Stimmt so?
Das Wort wird akzeptiert, ja.
> Ich denke, dass die Sprache wohl so aussehen sollte:
> [mm]L=\{0^n 1^{n+1} | n \in \mathbb N\}[/mm]. Die Anzahl der 0en,
> die vor den 1en kommen, muss um eins kleiner sein als die
> Anzahl der 1en. Richtig?
Naja. Wie ich weiter oben schon sagte. Schau doch einfach mal den "einfachsten" Fall an. Das Wort #01#. Wird das akzeptiert?
Gruß
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:39 Di 28.05.2013 | | Autor: | bandchef |
> Naja. Wie ich weiter oben schon sagte. Schau doch einfach mal den "einfachsten" Fall an. Das Wort #01#. Wird das akzeptiert?
[mm] $\# \underline{0} [/mm] 1 [mm] \#$: [/mm] Im ersten Schritt steht der Lese/Schreibkopf auf der 1. Er liest eine 1 ersetzt sie mit einer 1 und geht einen Schritt nach rechts. Dann sind wir hier: [mm] $\#0\underline{1} \#$ [/mm] Nun liest die TM im Zustand q1 eine 1. Sie ersetzt die 1 mit einer 1 und geht nach rechts und wechselt in q2: [mm] $\#01\underline{#}$. [/mm] Dann liest sie das # ersetzt sie mit # geht nach links und wechselt in q3: [mm] $\#0\underline{1} \#$. [/mm] In q3 liest sie die 1 ersetzt die 1 mit #, geht einen Schritt nach links und wechselt in q4: [mm] $\#\underline{0}\# \#$. [/mm] In q4 liest sie die 0 ersetzt sie mit 0 geht nach links und bleibt in q4: [mm] $\underline{#} [/mm] 0 ##$. In q4 liest sie # ersetzt sie mit # geht nach rechts und wechselt in q5: [mm] $#\underline{0}##$. [/mm] In q5 liest sie 0 ersetzt 0 mit # geht nach rechts und wechselt in q6. In q6 liest sie # ersetzt mit # und wechselt in q8 und akzeptiert so.
Richtig?
Hm, ok. Wenn nun 01 auch akzeptiert wird dann muss ich wohl die Sprache so umschreiben:
[mm] $L=\{0^n 1^m | n,m \in \mathbb N, n\leq m\}$
[/mm]
Stimmt's jetzt?
|
|
|
| |
|
Hallo bandchef,
> [mm]\# \underline{0} 1 \#[/mm]: Im ersten Schritt steht der
> Lese/Schreibkopf auf der 1. Er liest eine 1 ersetzt sie mit
Nein, er liest zuerst eine Null (Zustand [mm] q_0) [/mm] und geht dann ein Feld nach rechts.
> einer 1 und geht einen Schritt nach rechts. Dann sind wir
> hier: [mm]\#0\underline{1} \#[/mm]
Ja.
> Nun liest die TM im Zustand q1 eine 1.
Richtig.
> Sie ersetzt die 1 mit einer 1 und geht nach rechts
> und wechselt in q2: [mm]\#01\underline{#}[/mm]. Dann liest sie das #
> ersetzt sie mit # geht nach links und wechselt in q3:
> [mm]\#0\underline{1} \#[/mm]. In q3 liest sie die 1 ersetzt die 1
> mit #, geht einen Schritt nach links und wechselt in q4:
> [mm]\#\underline{0}\# \#[/mm]. In q4 liest sie die 0 ersetzt sie mit
> 0 geht nach links und bleibt in q4: [mm]\underline{#} 0 ##[/mm]. In
> q4 liest sie # ersetzt sie mit # geht nach rechts und
> wechselt in q5: [mm]#\underline{0}##[/mm]. In q5 liest sie 0 ersetzt
> 0 mit # geht nach rechts und wechselt in q6. In q6 liest
> sie # ersetzt mit # und wechselt in q8 und akzeptiert so.
>
> Richtig?
Ja, richtig.
> Hm, ok. Wenn nun 01 auch akzeptiert wird dann muss ich wohl
> die Sprache so umschreiben:
>
> [mm]L=\{0^n 1^m | n,m \in \mathbb N, n\leq m\}[/mm]
>
> Stimmt's jetzt?
 So ihr denn [mm] \IN [/mm] ohne Null definiert habt.
Gruß
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:52 Mi 29.05.2013 | | Autor: | bandchef |
> So ihr denn ohne Null definiert habt.
Ja, das haben wir!
Danke für deine Hilfe!
|
|
|
|
