Automatentheorie < Sonstiges < Lin. Algebra/Vektor < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:51 Mi 18.05.2011 | | Autor: | bandchef |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Es sei folgende Sprache L gegeben:
$L = \{ w \in \Sigma^{\star}_{\text{Bool}} | w \text{ endet auf 01}} \}$
Geben sie einen DEA an. |
Hey Leute!
Ich soll jetzt hier quasi einen "deterministischen endlichen Automaten" aufzeichnen. Könnt ihr mir helfen wie man das macht? Grundkenntnisse hab ich natürlich. Er braucht akzeptierende Zustände, einen Anfangszustand und es geht immer nur mit einer 0 oder 1 weiter.
Könnt ihr mir helfen?
|
|
| |
|
> Es sei folgende Sprache L gegeben:
>
> [mm]L = \{ w \in \Sigma^{\star}_{\text{Bool}} | w \text{ endet auf 01}} \}[/mm]
>
> Geben sie einen DEA an.
>
>
> Hey Leute!
>
> Ich soll jetzt hier quasi einen "deterministischen
> endlichen Automaten" aufzeichnen. Könnt ihr mir helfen wie
> man das macht? Grundkenntnisse hab ich natürlich. Er
> braucht akzeptierende Zustände, einen Anfangszustand und
> es geht immer nur mit einer 0 oder 1 weiter.
>
> Könnt ihr mir helfen?
Hallo bandchef,
ich denke, dass man einen solchen "DEA" zunächst
in Form eines gerichteten Graphen skizzieren kann.
So wie ich es sehe, kommt man in dem Beispiel
mit einem Graphen mit 4 Knoten aus.
[mm] q_0 [/mm] ist der Startknoten (noch kein Zeichen eingegeben).
Die Pfeile zeigen an, in welchen neuen Zustand der
Automat jeweils gehen muss, je nachdem welches
Zeichen gerade eingegeben wurde.
Ist nach Eingabe der gesamten zu prüfenden Zeichen-
sequenz der Automat im "finalen" Zustand [mm] q_3 [/mm] ,
so war die eingegebene Sequenz ein "Wort" von L,
andernfalls nicht.
LG Al-Chw.
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: jpeg) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:46 Do 19.05.2011 | | Autor: | bandchef |
Hi!
Zitat: "ich denke, dass man einen solchen "DEA" zunächst
in Form eines gerichteten Graphen skizzieren kann."
Und um genau das skizzieren geht es mir. Wie kann man aus der Vorschrift für die zu Erkennende Sprache genau diesen DEA wie du ihn gezeichnet hast ableiten und aufmalen? Das ist das woran ich scheitere...
|
|
|
| |
|
> Hi!
>
> Zitat: "ich denke, dass man einen solchen "DEA" zunächst
> in Form eines gerichteten Graphen skizzieren kann."
>
>
> Und um genau das skizzieren geht es mir. Wie kann man aus
> der Vorschrift für die zu Erkennende Sprache genau diesen
> DEA wie du ihn gezeichnet hast ableiten und aufmalen? Das
> ist das woran ich scheitere...
Nun ja, ich habe zunächst die ![[]](/images/popup.gif) Definition bei Wiki
nachgeschlagen und mir überlegt, dass hier wohl ein
ziemlich einfacher Graph ausreichen würde. Von jedem
Zustand [mm] q_i [/mm] muss je ein Pfeil mit "0" oder "1" zum
jeweils neuen Zustand [mm] \delta(q_i,0) [/mm] bzw. [mm] \delta(q_i,1) [/mm] zeigen. Außer
dem Startzustand [mm] q_0 [/mm] (noch keine Ziffer eingegeben)
muss es den akzeptierenden Zustand geben, der nur
erreicht werden kann, wenn gerade eine 1 und unmit-
telbar vorher eine 0 eingegangen ist. Also muss zwischen
[mm] q_0 [/mm] und dem akzeptierenden Zustand jedenfalls noch
ein Zustand [mm] q_1 [/mm] stehen, der nur durch eine "0" erreicht
werden kann und von dem aus eine "1" zum akzeptierenden
Zustand führt. Der Zustand [mm] q_2 [/mm] in meinem Graph ist dann
noch nötig für den Fall, dass eine "1" ohne eine unmit-
telbar davor stehende "0" erscheint.
So einen Graph zu skizzieren ist wohl Übungssache.
Ich habe genau dies zwar vorher noch nie gemacht,
hatte aber in etwas anderem Zusammenhang gerade
mit gerichteten Graphen zu tun. Man muss sich halt
bei jedem einzelnen Knoten klar machen, was da
beim Eintreffen einer neuen Ziffer einer Sequenz
genau geschieht bzw. geschehen soll. Um den Graph
zu entwerfen, ist es wohl am besten, vom akzeptie-
renden Zustand auszugehen und dann "rückwärts"
zu gehen. Etwas schwieriger wird es bestimmt,
wenn mehr als ein akzeptierender Zustand vor-
handen ist.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:07 Do 19.05.2011 | | Autor: | Teufel |
Hi!
3 Zustände reichen auch, oder? [mm] q_2 [/mm] brauchst du streng genommen gar nicht.
Nimm den mal raus und mach folgende Änderungen:
[mm] q_0 [/mm] mit 1 geht wieder auf sich selbst
[mm] q_3 [/mm] mit 1 geht auf [mm] q_0
[/mm]
|
|
|
| |
|
> Hi!
>
> 3 Zustände reichen auch, oder? [mm]q_2[/mm] brauchst du streng
> genommen gar nicht.
>
> Nimm den mal raus und mach folgende Änderungen:
> [mm]q_0[/mm] mit 1 geht wieder auf sich selbst
> [mm]q_3[/mm] mit 1 geht auf [mm]q_0[/mm]
Hab ich mir schon auch gedacht - aber mein Automat
hat den Vorteil, dass er erst dann Strom braucht,
wenn überhaupt Daten eingehen (Eingang einer Ziffer
startet erst die Stromversorgung für die ganze
Maschine ...)
Das ist doch wichtig in einer Zeit, wo man über
den im Standby verschwendeten Strom klagt ! 
LG Al
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:54 Do 19.05.2011 | | Autor: | Teufel |
Da haste Recht. :>
Verzeihung!
|
|
|
|
