Sprache: ohne Teilwort 'bb' < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:18 Di 09.02.2010 | | Autor: | RalU |
| Aufgabe | geg.: Alphabet [mm] \summe_ [/mm] = {a,b}
ges.: Sprache L, mit allen Wörten aus [mm] \summe_ [/mm] bei denen das Teilwort 'bb' nicht vorkommt. |
Ich würde folgendes vorschlagen:
L=_{def} = [mm] \overline{(bb)^{+}}
[/mm]
Allerdings weiß ich, dass dies nicht korrekt ist. Aber ich weiß nicht, warum...
denn [mm] {bb}^{+} [/mm] würde mir doch alle Teilwörter liefern und davon die Negation davon eben nicht diese Teilwörter.
Aber was ist z.B. mit dem Wort w=abb ? Darf ich das bilden?
Gruß, Ralf
|
|
| |
|
Hallo Ralf,
> Allerdings weiß ich, dass dies nicht korrekt ist. Aber ich
> weiß nicht, warum...
>
> denn [mm]{bb}^{+}[/mm] würde mir doch alle Teilwörter liefern und
> davon die Negation davon eben nicht diese Teilwörter.
Wie würdest Du damit beispielsweise das Wort aba bilden wollen?
Du erkennst warum das falsch ist?
> Aber was ist z.B. mit dem Wort w=abb ? Darf ich das
> bilden?
Nein, denn es enthält ja das Teilwort "bb".
Es können a's soviel hintereinander kommen wie wollen, aber es darf nur immer höchstens ein b zwischen den a's stehen bzw. am Anfang oder am Ende des Wortes.
Hilft Dir das schon als Tipp für die Bildung von L?
Gruß,
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:43 Di 09.02.2010 | | Autor: | RalU |
| Aufgabe | | L soll keine teilwörter 'bb' enthalten. |
> > denn [mm]{bb}^{+}[/mm] würde mir doch alle Teilwörter liefern und
> > davon die Negation davon eben nicht diese Teilwörter.
>
> Wie würdest Du damit beispielsweise das Wort aba bilden
> wollen?
> Du erkennst warum das falsch ist?
Ich versteh nicht ganz, warum [mm] \overline{{bb}^{+}} [/mm] mir nicht alle anderen Wörter des Alphabetes außer die Teilwörter liefert. Mein Alphabet war ja [mm] \summe= [/mm] { a,b }.
anderes Beispiel (passt nicht direkt zur Aufgabe): wenn ich nun [mm] L'=\overline{a} [/mm] als Sprache bilde, sind dass dann nicht folgende Wörter?
[mm] L'={\varepsilon,b,ab,ba,abb,baa,aba,bab,aa,abaa,....}, [/mm] also eben alle Wörter außer dem a ? Genauso würde es sich doch dann mit dem [mm] \overline{{bb}^{+}} [/mm] verhalten.
anderer Ansatz zur Lösung:
L = [mm] \summe [/mm] (hoch *) / {a,b}{hoch *} {bb} {a,b}{hoch *}
- alle Wörter des Alphabets außer
- Wörter die ein Teilwort bb enthalten
allerdings weiß ich nicht, ob das die einfachste Lösung ist.
Gruß, Ralf
|
|
|
| |
|
Hallo Ralf,
> Ich versteh nicht ganz, warum [mm]\overline{{bb}^{+}}[/mm] mir nicht
> alle anderen Wörter des Alphabetes außer die Teilwörter
> liefert. Mein Alphabet war ja [mm]\summe=[/mm] { a,b }.
>
> anderes Beispiel (passt nicht direkt zur Aufgabe): wenn ich
> nun [mm]L'=\overline{a}[/mm] als Sprache bilde, sind dass dann nicht
> folgende Wörter?
> [mm]L'={\varepsilon,b,ab,ba,abb,baa,aba,bab,aa,abaa,....},[/mm]
> also eben alle Wörter außer dem a ? Genauso würde es
> sich doch dann mit dem [mm]\overline{{bb}^{+}}[/mm] verhalten.
Also ich habe das eh noch nie bei der Definition einer Sprache benutzt und müsste jetzt mal in meinen Scripten schauen, inwiefern die Negation da zugelassen ist. (Bei regulären Ausdrücken/Sprachen sowieso nicht). Das Komplement einer Sprache, ja, das gibt es. Aber darum geht es hier ja gerade nicht, sondern Du willst ja die Sprache definieren. Unabängig davon, so rein spontan würde für mich [mm] \overline{a} [/mm] doch eher bedeuten = b und nicht = alle Wörter ohne dem Wort a.
>
> anderer Ansatz zur Lösung:
>
> L = [mm]\summe[/mm] (hoch *) / {a,b}{hoch *} {bb} {a,b}{hoch *}
>
> - alle Wörter des Alphabets außer
> - Wörter die ein Teilwort bb enthalten
Hm, das Komma zwischen {a,b} soll heißen entweder a oder b? Wenn dem so ist, dann könnte ich ja schon mit [mm] \{a,b\}\ [/mm] hoch* bb bilden - oder bbb usw. Und warum kommt bei dir danach {bb}? Genau das darf doch nie vorkommen. Nach deiner Definition wären Wörter möglich wie bbbbbb oder abbabb usw.
Gruß,
Anna
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:51 Mi 10.02.2010 | | Autor: | RalU |
> > anderer Ansatz zur Lösung:
> >
> > L = [mm]\summe[/mm] (hoch *) / ( {a,b}{hoch *} {bb} {a,b}{hoch *} )
> >
Ich will damit bezwecken, dass ich zunächst mein gesamtes Alphabet hernehme.
Dann schließe ich davon durch Differenzbildung (Mengenoperation) diejenigen Wörter auß, die ich nicht bilden darf ( innerhalb der roten Klammern)
Das müßte doch funktionieren.
Aber vielleicht gibt es ja eine wesentlich einfachere Lösung und ich komm nur nicht drauf....
Gruß, Ralf
|
|
|
| |
|
Hallo Ralf,
> > > anderer Ansatz zur Lösung:
> > >
> > > L = [mm]\summe[/mm] (hoch *) / ( {a,b}{hoch *} {bb} {a,b}{hoch *} )
> > >
> Ich will damit bezwecken, dass ich zunächst mein gesamtes
> Alphabet hernehme.
> Dann schließe ich davon durch Differenzbildung
> (Mengenoperation) diejenigen Wörter auß, die ich nicht
> bilden darf ( innerhalb der roten Klammern)
> Das müßte doch funktionieren.
>
> Aber vielleicht gibt es ja eine wesentlich einfachere
> Lösung und ich komm nur nicht drauf....
Naja, ich würd mir einfach überlegen, was für Wörter gebildet werden dürfen.
Und zwar alle in der Art:L = [mm] \{a | ab\}^{sternchen}
[/mm]
Damit haben wir schon alle Wörter über dem Alphabet abgedeckt, die kein Teilwort bb enthalten - außer den einen Spezialfall, dass das Wort mit einem b beginnt.
Berücksichtigt man den noch, dann kommt man auf
L = [mm] \{a | ab\}^{sternchen} \cup \{b\} \{a | ab\}^{sternchen}
[/mm]
So würde ich es spontan definieren.
Gruß
Anna
|
|
|
| |
|
Hallo Ralf,
vielleicht noch einmal hierzu:
> anderes Beispiel (passt nicht direkt zur Aufgabe): wenn ich
> nun [mm]L'=\overline{a}[/mm] als Sprache bilde, sind dass dann nicht
> folgende Wörter?
> [mm]L'={\varepsilon,b,ab,ba,abb,baa,aba,bab,aa,abaa,....},[/mm]
> also eben alle Wörter außer dem a ?
Vielleicht verwechselst Du das mit dem Komplement einer Sprache? Würdest Du nun eine Sprache L definieren, die nur das Wort a zulässt, dann enthält das Komplement [mm] \overline{L} [/mm] alle Worte, die in [mm] \Sigma^{sternchen} [/mm] enthalten sind, aber nicht in L.
Gruß
Anna
|
|
|
|
