www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Formale Sprachen" - reguläre Ausdrücke
reguläre Ausdrücke < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

reguläre Ausdrücke: Idee
Status: (Frage) beantwortet Status 
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

        
Bezug
reguläre Ausdrücke: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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?




Bezug
                
Bezug
reguläre Ausdrücke: Idee
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                        
Bezug
reguläre Ausdrücke: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
reguläre Ausdrücke: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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. :-)

Bezug
        
Bezug
reguläre Ausdrücke: Antwort
Status: (Antwort) fertig Status 
Datum: 16:06 So 17.11.2013
Autor: mtr-studi

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?

Bezug
                
Bezug
reguläre Ausdrücke: Idee
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
reguläre Ausdrücke: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                
Bezug
reguläre Ausdrücke: Idee
Status: (Frage) beantwortet Status 
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

Bezug
                                        
Bezug
reguläre Ausdrücke: Antwort
Status: (Antwort) fertig Status 
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]
Bezug
                                                
Bezug
reguläre Ausdrücke: Rückfrage
Status: (Frage) beantwortet Status 
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


Bezug
                                                        
Bezug
reguläre Ausdrücke: Antwort
Status: (Antwort) fertig Status 
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      







Bezug
                                                                
Bezug
reguläre Ausdrücke: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

>
>
>
>  


Bezug
                                                                        
Bezug
reguläre Ausdrücke: Antwort
Status: (Antwort) fertig Status 
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  



  

Bezug
                                                                                
Bezug
reguläre Ausdrücke: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:24 Di 19.11.2013
Autor: tunahan

Hallo Erdi es hat gut geklappt,
vielen Dank für deine Hilfe,
viele Gruesse,
tunahan

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Formale Sprachen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de