---

Geschrieben von KleenEule am 19.06.2011 um 13:48:

  regulärer Ausdruck darf 010 nicht enthalten

Meine Frage:
Guten Tag: Ich habe hier eine Frage zu den regulären Ausdrücken. Hier die Aufgabe:

Gib reguläre Ausdrücke für die folgenden Sprachen über Sigma = {0,1} an:
(a) L1 = {w | w enthält nicht das Wort 010}

Meine Ideen:
Unsere Idee war erst, das wir (1)(0*111*0*)*(1) nehmen. Haben aber im Endeffekt rausgefunden, dass des nicht wirklich stimmt.
Kann uns da jmd weiterhelfen?

---

Geschrieben von zockermax am 19.06.2011 um 14:42:

 

Mein Problem ist das Wort "enthält nicht". Ich habe den Reg Ex für w<>010. Bist du dir sicher, dass das "enthält nicht" heißen muss?

Gruß Max

---

Geschrieben von KleenEule am 19.06.2011 um 15:35:

 

Japp 100% sicher, habe die Aufgabe absichtlich direkt kopiert, damit keine fehler passieren.

DAs ist aber auch das, was uns persönlich zweifeln lässt , also das "enthält nicht"

---

Geschrieben von zockermax am 19.06.2011 um 16:13:

 

Also w ist doch bestimmt Element von Sigma.

->w sind alle bildbaren wörter aus Sigma.
-> w enthält nicht das Wort 010.
-> w sind alle Wörte Sigma bis auf das Wort 010.

Also würde die L1 0010 akzeptieren.

Gruß max

---

Geschrieben von zockermax am 19.06.2011 um 16:38:

 

(1(1|0)*)* | (0 ( 0 (1|0)*)*) | (01(1(1|0)*)*) | ( 010 ( 1|0 )+)

---

Geschrieben von ed209 am 19.06.2011 um 21:19:

 

Ich komme auf einen wesentlich kürzeren Ausdruck.
Mir hilft es dazu den DEA dazu zu konstruiieren, der Ausdruck ist dann relativ einfach daraus abzulesen.

Gruß
ED

PS: Man kann auch damit anfangen den Automaten zu finden der das Komplement der Sprache enthält. (also die Wörter die 010 enthalten), das ist intuitiver.

---

Geschrieben von zockermax am 19.06.2011 um 21:38:

 

Kannst du mal bitte den kürzeren Regulären Ausdruck angeben?

Außerdem schreibst du auch "Wörter die 010 enthalten", aber eigentlich akzeptiert die Sprache L1 alle Wörter außer dem Wort 010.

Gruß Max

---

Geschrieben von Karlito am 19.06.2011 um 21:44:

 

Hier ist die Frage wie die Aufgabe gemeint ist...

Kann auch sein, dass es so gewollt ist, dass kein Infix 010 erlaubt ist...

Ich glaube, wenn nur das Wort 010 nicht erlaubt ist, dann ist die Aufgabe zu trivial...

VG,

Karlito

---

Geschrieben von Karlito am 19.06.2011 um 21:50:

 

Der Ausdruck, welcher nur das Wort 010 nich zulässt wäre (00+11+10)(0+1)*

Wenn ich mich nicht verhauen habe, wäre das viel zu einfach...

VG,

Karlito

---

Geschrieben von ed209 am 19.06.2011 um 21:54:

 

Zitat:

Kann auch sein, dass es so gewollt ist, dass kein Infix 010 erlaubt ist...

Genau so wird es gemeint sein: Jedes Wort in dem nicht 010 enthalten ist.

@zockermax:

Es geht hier nicht darum die Lösung vorzusagen. Idee des Forum ist es Hinweise zum Lösungsweg zu geben, damit man es lernt, nicht die Lösung damit man den Übungszettel nicht selber machen muß.

Gruß,
ED

---

Geschrieben von Karlito am 19.06.2011 um 22:05:

 

Der Weg des sturen Algorithmensklaven:

DEA für Sprache, die 010 enthält, Konstruieren -> Komplement bilden -> Arden Lemma

VG,

Karlito

---

Geschrieben von zockermax am 19.06.2011 um 22:34:

 

Ähhh?????????????

Dein entwickelter Reg Ex (00+11+10)(0+1)*, akzeptiert aber zb nicht das Wort 1 oder das Wort 0, obwohl es in der Sprache L1 liegt.

---

Geschrieben von Karlito am 19.06.2011 um 22:39:

 

Zitat:

Original von zockermax Ähhh????????????? Dein entwickelter Reg Ex (00+11+10)(0+1)*, akzeptiert aber zb nicht das Wort 1 oder das Wort 0, obwohl es in der Sprache L1 liegt.

Stimmt Irgendwie mögen Fehler meine Ergebnisse

(0+1+(00+11+10)(0+1)*) sollte es aber machen, oder?

VG,

Karlito

---

Geschrieben von KleenEule am 20.06.2011 um 02:07:

 

Wie sicher bist du dir dem?

Also wir haben nun noch weiter geforscht und kamen auf:
1*0*+(1*0*011)*1*0*01(10+1*)

---

Geschrieben von Karlito am 20.06.2011 um 08:22:

 

Hi,

sorry für das wirrwar. Wie weiter oben beschrieben, löst der Ausdruck wahrscheinlich leider nicht euer Problem. Der Ausdruck akzeptiert alle Wörter über der Sprache Sigma* ohne das Wort 010. Eure Aufgabe ist sicherlich, dass die Sprache den Infix 010 nicht enthält...

Wie ed beschrieben hat, is es günstig, einen DEA zu bauen, welcher Wörter mit dem Infix 010 akzeptiert und dann das komplement zu bilden. Er meinte man kann dann den Ausdruck rel. einfach ermitteln (durch nachdenken).

Als Erweiterung dessen kann man noch das Arden Lemma verwenden um den Ausdruck aus dem DEA zu "errechnen".

VG,

Karlito