Formale Sprachen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:50 Di 28.08.2007 | | Autor: | Linkin |
Hallo alle,
kann mir jemand bitte kurz erklären was folgende Ausdrücke auf einem {a,b} Alphabet zu bedeuten haben:
1- a* wenn es in einem Ausdruck steht
2-(a ∪ b) "a vereinigt b"
3-(a ∪ b)* das kann ich leider gar nicht blicken :(
4-z.b aa*?
vielen Dank Leute
*Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. *
|
|
| |
|
Hallo Linkin!
> kann mir jemand bitte kurz erklären was folgende Ausdrücke
> auf einem {a,b} Alphabet zu bedeuten haben:
> 1- a* wenn es in einem Ausdruck steht
Wo soll es denn sonst stehen, wenn es nicht in einem Ausdruck steht? Jedenfalls steht a* für eine beliebige Wiederholung von a. Das kann also a sein oder auch aa oder aaaaaaaa oder noch viel mehr a's. Bin mir allerdings gerade nicht sicher, ob es auch "kein a" heißen kann - es gibt auch noch [mm] a^{+} [/mm] - falls ihr das hattet, das bedeutet "ein oder kein a" und falls ihr mit [mm] \omega-\mbox{Sprachen} [/mm] arbeitet, gibt es noch [mm] a^{\omega}, [/mm] das bedeutet "unendlich viele a's". a* gibt also auf jeden Fall eine endliche Menge an a's an.
> 2-(a ∪ b) "a vereinigt b"
Das finde ich eine eher seltsame Schreibweise, ich kenne da nur (a+b), und das bedeutet "entweder a oder b".
> 3-(a ∪ b)* das kann ich leider gar nicht blicken :(
Na, vielleicht weißt du das jetzt? Das bedeutet ja einmal, dass du entweder ein a oder ein b hast und der Stern gibt dann noch an, dass du davon beliebig viele hast. Und zwar können das dann nur a's sein oder nur b's oder auch abwechselnd a's und b's oder eine beliebige Kombination von a's und b's - aber auch wieder nur endlich viele.
> 4-z.b aa*?
Das bedeutet, dass als erstes auf jeden Fall ein a steht, und dahinter noch beliebig viele a's. 
Alle Klarheiten beseitigt? Ansonsten frage gerne nochmal nach. ![[sunny]](/images/smileys/sunny.gif "[sunny]")
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:39 Di 28.08.2007 | | Autor: | Linkin |
Vielen Dank Bastiane,
aber die folgende Aufgabe konnte ich nicht verstehen:
Aufgabe: die formale Sprache L sei die Menge aller Wörter über dem Alphabet {a,b},die höchstens 2 mal das Zeichen b enthalten oder deren viert-letztes Zeichen das Zeichen a ist.
Lösung:a*+a*ba*+a*ba*ba*+(a+b)*a(a+b)(a+b)(a+b)
=a*(b+E)a*(b+E)a*+(a+b)*a(a+b)(a+b)(a+b)
mit E ist epsilon gemeint und + ist vereinigt.
Also was meint er mit dem viert-letzten und Wieso gibt´s am Ende 3 mal (a+b)?
Das Thema macht mich wahnsinnig,kann mir jemand Helfen?
Es wäre voll nett und lieb.
Danke im Voraus
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:07 Di 28.08.2007 | | Autor: | Mumrel |
Hi,
ich wills mal veruschen.
> Aufgabe: die formale Sprache L sei die Menge aller Wörter
> über dem Alphabet {a,b},die höchstens 2 mal das Zeichen b
> enthalten oder deren viert-letztes Zeichen das Zeichen a
> ist.
>
> =a*(b+E)a*(b+E)a*+(a+b)*a(a+b)(a+b)(a+b)
Wenn du das vernünftig klammerst kann man das auch lesen!
[a* (b+E) a* (b+E) a*] + [(a+b)* a (a+b) (a+b) (a+b)]
Also der erste Teil erlaubt maximal zwei b's (auch keines) in einer Folge von a unterzubringen. Der erste Teil kann auch komplett leer sein.
Beachte a* kann auch gar nichts sein, man kann die zwei b's also auch hintereinander machen.
Mögiches Wort damit:
aaa b a E a = aaabaa (ok, enthält ein b).
Der zweite Teil als Alternative zum ersten Teil.
(a+b)* erlaubt erstmal eine beliebige lange Zeichenkette (wieder auch die Zeichenkette der Länge 0!) die nur aus a's und b's bestehen.
Also z.B. "" oder "aaaa" oder "abbabbbababba".
Dann kommt das erwzungene a, das ja Bedinung ist (vierletztes Zeichen muss! ein a sein)
Und danach muss man sich drei mal zwischen a und b entscheiden.
Man muss sich dreimal entscheiden, weil es ja sonst kein vierletztes Zeichen geben kann, d.h. nach der erzwungenen a müssen noch drei Zeichen kommen.
Das wird dann eben über (a + b) erreicht.
Viele Grüße
Mumrel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:16 Di 28.08.2007 | | Autor: | Linkin |
Vielen Dank Mumrel,war sehr nett von dir
|
|
|
|
