det. endlicher Automat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:35 So 03.01.2010 | | Autor: | LiN24 |
| Aufgabe | Erstellen Sie folgende deterministische endl. Automaten, die folgende Sprachen über dem Alphabet {0,1} akzeptieren:
c) Menge aller mit einer 1 beginnenden Zeichenketten, interpretiert als binäre ganze Zahl, die kongruent zu 0 mod 5 ist.
d) Menge aller Zeichenketten, deren 3.letztes Symbol eine 1 ist.
e) Menge aller Zeichenketten, deren 10.letztes Symbol eine 1 ist. |
Hallo,
ich habe bei den 3 Teilaufgaben keine Ahnung, wie ich die Automaten aufstellen kann, bei d) und e) hab ich nicht mal ne Idee für die Umsetzung...bei c) hab ich mir überlegt gehabt, dass man was mit den restklassen machen müsste, also Zustände für 0, 1, 2, 3, 4 als Rest, aber mir fehlt da die Umsetzung.
Würde mich freuen, wenn mir jemand weiter helfen könnte.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:32 Mo 04.01.2010 | | Autor: | bazzzty |
> Erstellen Sie folgende deterministische endl. Automaten,
> die folgende Sprachen über dem Alphabet {0,1}
> akzeptieren:
> c) Menge aller mit einer 1 beginnenden Zeichenketten,
> interpretiert als binäre ganze Zahl, die kongruent zu 0
> mod 5 ist.
> d) Menge aller Zeichenketten, deren 3.letztes Symbol eine
> 1 ist.
> e) Menge aller Zeichenketten, deren 10.letztes Symbol eine
> 1 ist.
Hallo LiN,
ich werde mal versuchen, Dir nur Tipps zu geben:
c) Stelle Dir vor, Du kennst den Rest einer Zahl xxxxx (modulo 5). Was sagt Dir das über den Rest von xxxx1 bzw xxxx0?
Beispiel: 1011 hat den Rest 1, welchen Rest hat 10110? Welchen 10111? Probier' mal zwei, drei Werte aus. Bekomme ein Gefühl dafür, was passiert. Und dann denke mal an die Basics der Restklassen - Man kann Restklassenoperationen immer vorziehen:
[mm][a*x+b] = [a*[x]+b][/mm].
d+e) Ist leichter, als Du denkst. Aber nicht so elegant, wie Du es vielleicht gerne hättest. Du wirst 8 Zustände brauchen, bei e) sogar 1024. Welche?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:23 Mo 04.01.2010 | | Autor: | LiN24 |
Hallo,
für d) hab ich jetzt einen Automaten aufstellen können:
A = ({0,1}, [mm] {z_{0}, z_{1}, ... , z_{7}}, z_{0}, {z_{3}, z_{4}, z_{6}, z_{7}}, \delta) [/mm] mit
[mm] \delta (z_{0}, [/mm] 0) -> [mm] (z_{0})
[/mm]
[mm] \delta (z_{0}, [/mm] 1) -> [mm] (z_{1})
[/mm]
[mm] \delta (z_{1}, [/mm] 0) -> [mm] (z_{5})
[/mm]
[mm] \delta (z_{1}, [/mm] 1) -> [mm] (z_{2})
[/mm]
[mm] \delta (z_{2}, [/mm] 0) -> [mm] (z_{4})
[/mm]
[mm] \delta (z_{2}, [/mm] 1) -> [mm] (z_{3})
[/mm]
[mm] \delta (z_{3}, [/mm] 0) -> [mm] (z_{4})
[/mm]
[mm] \delta (z_{3}, [/mm] 1) -> [mm] (z_{3})
[/mm]
[mm] \delta (z_{4}, [/mm] 0) -> [mm] (z_{7})
[/mm]
[mm] \delta (z_{4}, [/mm] 1) -> [mm] (z_{6})
[/mm]
[mm] \delta (z_{5}, [/mm] 0) -> [mm] (z_{7})
[/mm]
[mm] \delta (z_{5}, [/mm] 1) -> [mm] (z_{6})
[/mm]
[mm] \delta (z_{6}, [/mm] 0) -> [mm] (z_{0})
[/mm]
[mm] \delta (z_{6}, [/mm] 1) -> [mm] (z_{0})
[/mm]
[mm] \delta (z_{7}, [/mm] 0) -> [mm] (z_{0})
[/mm]
[mm] \delta (z_{7}, [/mm] 1) -> [mm] (z_{0})
[/mm]
bei e) wäre dies analog, man bräuchte wieder für jede Alternative einen Zustand, damit [mm] 2^{10} [/mm] Zustände, aber wie kann ich das allg. formulieren, denn 1024 Zustände aufschreiben, kann ja nicht Sinn und Zweck der Aufgabe sein
bei c) erkenn ich bei dem Bsp. dass bei 1011 der Rest 1 ist und bei 10110 der Rest 2 und bei 10111 der Rest 3, da ich immer nur an der Position [mm] 2^{0} [/mm] was hinzufügen kann und die andern Plätze sich verschieben, hab ich bei ner hinzukommenden 0 die Verdopplung und bei 1 die Verdopplung plus 1
mein Problem ist jetzt noch, wie ich den Automaten aufstellen kann, könntet ihr mir da bitte weiter helfen?
Danke schonmal für die Tipps bis jetzt!
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:29 Mo 04.01.2010 | | Autor: | bazzzty |
> für d) hab ich jetzt einen Automaten aufstellen können:
> A = ({0,1}, [mm]{z_{0}, z_{1}, ... , z_{7}}, z_{0}, {z_{3}, z_{4}, z_{6}, z_{7}}, \delta)[/mm]
Ich glaube Dir einfach mal, dass Du den hinbekommen hast. Mein Tipp wäre noch, die Zustände binär zu numerieren, dann ist es leichter, den Überblick zu behalten, also
[mm]\delta (z_{101},[/mm] 0) -> [mm](z_{010})[/mm]
> bei e) wäre dies analog, man bräuchte wieder für jede
> Alternative einen Zustand, damit [mm]2^{10}[/mm] Zustände, aber wie
> kann ich das allg. formulieren, denn 1024 Zustände
> aufschreiben, kann ja nicht Sinn und Zweck der Aufgabe
> sein
Nein, sicher nicht. Zunächst endthält die Zustandsmenge [mm]z_0[/mm] bis [mm]z_{1023}[/mm], aber für die Übergangsregeln und die Akzeptierenden Zustände kannst Du binäre Indizes verwenden, also Knoten als
[mm]z_{(a_9\cdots a_0)_2[/mm] bezeichnen.
Wie sieht dann in zwei Zeilen die Übergangsfunktion aus?
Wie würdest Du die Menge der akzeptierenden Zustände beschreiben?
> bei c) erkenn ich bei dem Bsp. dass bei 1011 der Rest 1 ist
> und bei 10110 der Rest 2 und bei 10111 der Rest 3, da ich
> immer nur an der Position [mm]2^{0}[/mm] was hinzufügen kann und
> die andern Plätze sich verschieben, hab ich bei ner
> hinzukommenden 0 die Verdopplung und bei 1 die Verdopplung
> plus 1
exakt.
> mein Problem ist jetzt noch, wie ich den Automaten
> aufstellen kann, könntet ihr mir da bitte weiter helfen?
Du bist doch schon fast fertig! Du weißt, wie sich der Rest ändert, wenn ein Zeichen gelesen wird. Wie viele mögliche Reste hast Du denn? Welche sind akzeptierend?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:34 Mo 04.01.2010 | | Autor: | LiN24 |
für c) hab ich jetzt die Lösung, jeweils einen Zustand für jede mögliche Restklasse also [mm] z_{0} [/mm] bis [mm] z_{4} [/mm] und einen Startzustand [mm] z_{s}, [/mm] der die 0 abfängt
bei e) sitz ich immernoch auf dem Schlauch, ich weiß nicht, wie ich das formulieren soll
Könntest du mir die Lösung bitte erklären?
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:40 Mo 04.01.2010 | | Autor: | bazzzty |
> bei e) sitz ich immernoch auf dem Schlauch, ich weiß
> nicht, wie ich das formulieren soll
>
> Könntest du mir die Lösung bitte erklären?
Gerne, ich versuch nochmal behutsam zu nachzuhelfen:
Alphabet ist wieder [mm]\{0,1\}[/mm], Zustände sind [mm]\{z_{0},\dots,z_{1023}[/mm], davon sind akzeptierend
[mm]\{z_{(1a_8a_7\cdots a_0)_2}: a8,\dots,a_0\in \{0,1\}\}[/mm].
Die Übergangsfunktion ist definiert durch
[mm]q(z_{(a_9\cdots a_0)_2},e)=??[/mm].
Na, klingelts?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:46 Mo 04.01.2010 | | Autor: | LiN24 |
ich würde jetzt im Startzustand wieder beginnen, aber da würde ich Kombinationen verlieren
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:05 Mo 04.01.2010 | | Autor: | bazzzty |
Ich verstehe Dich leider nicht. Du beginnst in Zustand [mm] z_{0000000000} [/mm] und wechselst nach [mm] z_{0000000001}. [/mm] Dann entweder nach [mm] z_{0000000010} [/mm] oder [mm] z_{0000000011} [/mm] usw. Die Schreibweise mit den [mm] a_i [/mm] ist doch nur symbolisch, um nicht alle 2000 möglichen Übergänge schreiben zu müssen: von [mm] z_{a_9a_8\cdots a_0} [/mm] wechselst Du nach [mm] z_{a_8a_7\cdots a_0 1} [/mm] oder [mm] z_{a_8a_7\cdots a_0 0}. [/mm] Wo genau ist das Problem?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:13 Mo 04.01.2010 | | Autor: | LiN24 |
Danke für die Hilfe, jetzt hab ich es verstanden 
|
|
|
|
