reguläre Ausdrücke < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:47 Fr 15.11.2013 | | Autor: | tunahan |
| Aufgabe | Geben Sie folgende Frage über {a,b,c} reguläre Ausdrücke an:
{ w | w enthält nicht die Teilfolge bc } |
ist diese Lösung richtig ?
[mm] (a,c)*(\epsilon [/mm] + b(b,a)*)
Ich bedanke mich
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:48 Sa 16.11.2013 | | Autor: | mtr-studi |
Für was habt ihr das [mm] \epsilon [/mm] definiert (leeres Zeichen)?
Soll man bei dieser Aufgabe aus {a,b,c} alle möglichen Folgen bilden unter Ausschluss der Teilfolge bc?
Die Folgen bac wäre z.B. in deinem Ausdruck nicht enthalten. Des Weiteren könnte man aus diesem Ausdruck auch Folgen mit unendlichen vielen Ausdrücken bilden durch die Iteration, ist das beabsichtigt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:31 So 17.11.2013 | | Autor: | tunahan |
Hallo vielen Dank,
> Für was habt ihr das [mm]\epsilon[/mm] definiert (leeres Zeichen)?
Ja ist als leeeres Zeichen definiert
> Soll man bei dieser Aufgabe aus {a,b,c} alle möglichen
> Folgen bilden unter Ausschluss der Teilfolge bc?
ja das stimmt auch,
>
> Die Folgen bac wäre z.B. in deinem Ausdruck nicht
> enthalten. Des Weiteren könnte man aus diesem Ausdruck
> auch Folgen mit unendlichen vielen Ausdrücken bilden durch
> die Iteration, ist das beabsichtigt?
Ja gerade hab auch bemerkt dass dieses Automat keinen
bac erkennt, wäre ich dankbar für weitere Tipps wie ich den
regulären Ausdruck bauen kann
>
>
>
mit besten Grüssen,
Tunahan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:00 So 17.11.2013 | | Autor: | Ebri |
Hallo,
ich habe die Aufgabe auch gemacht und mir war der RA auch nicht sofort klar.
Meine Lösung: Einen NFA bauen, der die Sprache erzeugt und daraus den RA bestimmen.
Gruß
Ebri
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:08 So 17.11.2013 | | Autor: | mtr-studi |
Ich denke du kannst ihm viel besser weiterhelfen. Da vorher niemand geantwortet hatte, habe ich nur mit meinem wenigen Wissen über reguläre Ausdrücke versucht zu helfen, aber ich denke es geht auf etwas Anderes hinaus.
Vielleicht kannst du ihm einen guten Tipp geben. 
|
|
|
| |
|
Ok,also ich gehe einfach mal davon aus, dass wir mit unserem regulären Ausdruck einfach erstmal nur folgende Folge aussperren möchten:
abc
bca
Das würde mit dem Ausdruck:
((b+c)(a)(b+c))+((a+c)(c+b)(a+b)) z.B. funktionieren, aber es sind auch wieder ungültige Eingaben möglich wie z.B. bab, cac usw., also unter Mehrfachverwendung der Buchstaben aus der Menge.
Mir fällt selber leider gerade kein Ausdruck ein, der die Buchstaben nur einfach jeweils verwendet und die anderen ausschließt, außer alle Kombinationen aufzuschreiben. :-/
Das wäre dann nämlich sowas wie:
(((c)(((a)(b))+((b)(a))))+((b)(a)(c))+((a)(c)(b)))
Damit könntest du dann wirklich nur die gültigen Folgen:
acb
bac
cab
cba
erzeugen, aber der Ausdruck ist natürlich extrem lang.
Könntest du die Aufgabenstellung vielleicht näher erläutern, was explizit verlangt ist?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:00 So 17.11.2013 | | Autor: | tunahan |
Hallo
Ich glaub habs gefunden erst mit Automat gebaut
dann Reguläre Ausdrücke extrahiert
so sieht meine Antwort hoffe dass es richtig ist
(a+c+ba)*+b*
Ich bedanke mich
LG tunahan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:30 So 17.11.2013 | | Autor: | Ebri |
Du bist auf dem richtigen Weg!
Dein RA sieht meinen recht ähnlich, aber ich glaube er stimmt noch nicht ganz. Zum Beispiel wird das Wort "bab" nicht erkannt.
Wie sieht dein Automat aus?
Gruß
Ebri
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:06 So 17.11.2013 | | Autor: | tunahan |
> Du bist auf dem richtigen Weg!
> Dein RA sieht meinen recht ähnlich, aber ich glaube er
> stimmt noch nicht ganz. Zum Beispiel wird das Wort "bab"
> nicht erkannt.
Ich glaube es wird doch erkannt bitte den letzten optionalen "+b"
im Auge behalten
> Wie sieht dein Automat aus?
automat besteht aus [mm] q_1 q_2 q_3 [/mm]
[mm] q_1 [/mm] und [mm] q_2 [/mm] Endzustand
[mm] q_1 [/mm] ~ [mm] (a+c)q_1
[/mm]
[mm] q_2 [/mm] ~ [mm] aq_1 [/mm] + [mm] b_q_2 [/mm] + [mm] cq_3
[/mm]
[mm] q_3 [/mm] ~ [mm] (a+b+c)q_3
[/mm]
>
> Gruß
> Ebri
Gruss
Tunahan
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:19 So 17.11.2013 | | Autor: | Ebri |
Das "+b*" hinten habe ich gesehen, "+" steht aber für die Vereinigung und nicht für das Komplexprodukt und kann im RA als "oder" gelesen werden.
Ich habe meinen Automat mal als Anhang beigefügt.
Gruß
Ebri
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:37 Mo 18.11.2013 | | Autor: | tunahan |
Hallo Ebri
> Das "+b*" hinten habe ich gesehen, "+" steht aber für die
> Vereinigung und nicht für das Komplexprodukt und kann im
> RA als "oder" gelesen werden.
>
> Ich habe meinen Automat mal als Anhang beigefügt.
>
Mein Automat ist das selber, ich hatte nur DFA Version ,
also ich meine mit + b bei Zustand [mm] q_1 [/mm] diese "b" Schleife
wie konnte man sonst diesen b bei Regulären Ausdruck
beschreiben?
Gruss
tunahan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:04 Mo 18.11.2013 | | Autor: | Ebri |
> Mein Automat ist das selber, ich hatte nur DFA Version,...
Da hast du recht, die Automaten sollten beide die gewünschte Sprache beschreiben. Aber ein DFA macht das Umwandeln in einen Regulären Ausdruck nur komplizierter (mehr Zustände und Übergänge).
Ich gehe jetzt mal von meinen NFA aus, dann ergibt sich folgendes Äquivalenzensystem:
[mm] x_{1} [/mm] ~ [mm] (a+c)x_{1} [/mm] + [mm] bx_{2} [/mm] + A*
[mm] x_{2} [/mm] ~ [mm] bx_{2} [/mm] + [mm] ax_{1} [/mm] + A*
Löst man dieses mithilfe der Resolutionsregel (*) auf, sollte man den korrekten RA bekommen.
(*):
Seien [mm] \alpha, \beta \in RA(\Sigma).
[/mm]
Wenn x ~ [mm] \alpha*x [/mm] + [mm] \beta [/mm] und [mm] \varepsilon \not\in [\alpha], [/mm] dann gilt: x ~ [mm] \alpha^\ast*\beta
[/mm]
Gruß
Ebri
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:22 Mo 18.11.2013 | | Autor: | tunahan |
> > Mein Automat ist das selber, ich hatte nur DFA Version,...
>
> Da hast du recht, die Automaten sollten beide die
> gewünschte Sprache beschreiben. Aber ein DFA macht das
> Umwandeln in einen Regulären Ausdruck nur komplizierter
> (mehr Zustände und Übergänge).
>
> Ich gehe jetzt mal von meinen NFA aus, dann ergibt sich
> folgendes Äquivalenzensystem:
>
> [mm]x_{1}[/mm] ~ [mm](a+c)x_{1}[/mm] + [mm]bx_{2}[/mm] + A*
> [mm]x_{2}[/mm] ~ [mm]bx_{2}[/mm] + [mm]ax_{1}[/mm] + A*
>
> Löst man dieses mithilfe der Resolutionsregel (*) auf,
> sollte man den korrekten RA bekommen.
>
> (*):
> Seien [mm]\alpha, \beta \in RA(\Sigma).[/mm]
> Wenn x ~ [mm]\alpha*x[/mm] +
> [mm]\beta[/mm] und [mm]\varepsilon \not\in [\alpha],[/mm] dann gilt: x ~
> [mm]\alpha^\ast*\beta[/mm]
Wäre dann (a+c+ba)*bb* die Lösung ?
LG
tunahan
>
>
>
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:46 Mo 18.11.2013 | | Autor: | Ebri |
> Wäre dann (a+c+ba)*bb* die Lösung ?
Ich komme auf etwas anderes. Also wir haben:
I [mm] x_{1} [/mm] ~ [mm] (a+c)x_{1} [/mm] + [mm] bx_{2} [/mm] + A*
II [mm] x_{2} [/mm] ~ [mm] bx_{2} [/mm] + [mm] ax_{1} [/mm] + A*
Resolutionsregel auf II mit [mm] \alpha [/mm] = b und [mm] \beta [/mm] = [mm] ax_{1} [/mm] + A* :
[mm] x_{2} [/mm] ~ [mm] b^\ast*(ax_{1} [/mm] + A*) ~ [mm] b^\ast*ax_{1} [/mm] + [mm] b^\ast
[/mm]
In I einsetzten:
[mm] x_{1} [/mm] ~ [mm] (a+c)x_{1} [/mm] + [mm] b(b^\ast*ax_{1} [/mm] + [mm] b^\ast) [/mm] + A*
~ [mm] (a+c)x_{1} [/mm] + [mm] bb^\ast*ax_{1} [/mm] + [mm] bb^\ast [/mm] + A*
~ [mm] (a+c+bb^\ast*a)x_{1} [/mm] + [mm] bb^\ast [/mm] + A*
Jetzt die Resolutionsregel auf das neue I und fertig.
Gruß
Ebri
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:24 Di 19.11.2013 | | Autor: | tunahan |
Hallo Erdi es hat gut geklappt,
vielen Dank für deine Hilfe,
viele Gruesse,
tunahan
|
|
|
|
