Formulierung einer Sprache < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Geben Sie die vom endlichen Automaten [mm] EA=(X,Z,f,q_{0},E) [/mm] erkannte Sprache L(EA) an. |
Hallo liebes Forum!
Ich habe für diese Aufgabe noch folgende Zeichnung bekommen:
[Dateianhang nicht öffentlich]
Nun bin ich schon so weit, dass ich erkannt habe, dass die Wörter erst vom Automaten akzeptiert werden, wenn zwei Mal hintereinander die selbe Zahl gekommen ist, der Rest des Wortes ist egal. Ich weiß jetzt nicht, wie ich das formulieren soll. Kann mir bitte jemand helfen?
lg monsterbacke
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
| |
|
Hallo monsterbacke!
> Geben Sie die vom endlichen Automaten [mm]EA=(X,Z,f,q_{0},E)[/mm]
> erkannte Sprache L(EA) an.
> Hallo liebes Forum!
>
> Ich habe für diese Aufgabe noch folgende Zeichnung
> bekommen:
> [Dateianhang nicht öffentlich]
> Nun bin ich schon so weit, dass ich erkannt habe, dass die
> Wörter erst vom Automaten akzeptiert werden, wenn zwei Mal
> hintereinander die selbe Zahl gekommen ist, der Rest des
> Wortes ist egal. Ich weiß jetzt nicht, wie ich das
> formulieren soll. Kann mir bitte jemand helfen?
>
> lg monsterbacke
Ich gehe mal davon aus, dass bei euch der nur einmal umrandete Zustand der Endzustand ist. Dann kannst du das doch hier genauso machen wie immer, einfach vorne anfangen und aufschreiben, was passiert. Also zuerst kommt entweder eine 0 oder eine 1, und je nachdem, was von beiden, kommt danach beliebig oft (10) oder (01) usw.
Ich probier's mal für den 0er Zweig, damit du selbst noch was zu tun hast:
0(10)*(11|0)(1|0)*
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Danke für die Antwort!
Also bei der 1 müsste das dann 1(01)*(00|1)*(0|1)* sein. Soll ich jetzt also schreiben
[mm] L(EA)=(0(10)^{a}(11|0)^{b}(1|0)^{c},1(01)^{a}(00|1)^{b}(0|1)^{c};a,b,c\in\IN) [/mm] oder gib´t es dafür eine verkürzte Fassung?
lg monsterbacke
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:17 Mi 11.03.2009 | | Autor: | bazzzty |
> Danke für die Antwort!
>
> Also bei der 1 müsste das dann 1(01)*(00|1)*(0|1)* sein.
> Soll ich jetzt also schreiben
>
> [mm]L(EA)=(0(10)^{a}(11|0)^{b}(1|0)^{c},1(01)^{a}(00|1)^{b}(0|1)^{c};a,b,c\in\IN)[/mm]
> oder gib´t es dafür eine verkürzte Fassung?
Ja, die gibt es, die entspricht nicht direkt dem Automaten, aber Du hast ja schon selbst zusammengefaßt, wir Wörter aussehen: Irgendwas, dann eine Dopplung, und dann wieder irgendwas, also schlicht
[mm]L(EA)=x_1(00)^a(11)^b x_2, x_1,x_2\in \Sigma^\star a,b\in \IN_0[/mm]
So würde ich auch auf die Frage antworten, wenn nicht explizit nach einer Darstellung gefragt ist, die sich aus dem dargestellten Automaten ablesen läßt.
|
|
|
| |
|
Mir hat immer dieses Thema gut gefallen, ich hoffe, ich erinnere mich daran.
Ich gebe dir eine "grobe"(nicht simplifiziert aber sie ist richtig!!!) Lösung, die Elegante solltest du finden, so wie die Beschreibung der mit deinen eigenen Worten
L = [mm] \varepsilon [/mm] + 0(10)* + 1(01)*
wobei [mm] \varepsilon [/mm] das leere Wort ist (wie du schon wissen solltest)
Grüsse
Branwijck
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:59 Mi 11.03.2009 | | Autor: | bazzzty |
> Ich gebe dir eine "grobe"(nicht simplifiziert aber sie ist
> richtig!!!) Lösung, die Elegante solltest du finden, so wie
> die Beschreibung der mit deinen eigenen Worten
>
> L = [mm]\varepsilon[/mm] + 0(10)* + 1(01)*
Ich wäre mit da nicht so sicher. Zum einen ist nach der Beschreibung von monsterbacke [mm]q_3[/mm] der akzeptierende Zustand, ich nehme an, dass Du die doppelt umrandeten für akzeptierend gehalten hast. Zum anderen ist dann die Lösung immer noch nicht korrekt, da sie das Wort 01 nicht enthält.
|
|
|
|
