 Thema: Pumping Lemma & Beweis für reguläre Sprache |
|
|
Hi,
ich bräuchte mal dringend Hilfe bei zwei Aufgaben:
1.) Ich soll beweisen oder widerlegen, dass folgende Sprache regulär ist.
L =die Sprache mit den Namen aller Studierenden.
Nun, da es sich um endliche Wörter mit endlicher Wortlänge handelt, nehme ich an, dass die Sprache regulär ist.
Dies könnte man ja z.B. mit einer Typ-3-Grammatik beweisen.
Also G= ({a-z}, {S}, P, S)
P = S -> Name1, Name1, ... NameN usw.
Wie könnte ich diese Typ-3-Grammatik beschreiben, damit die Sprache vollständig erfüllt ist.
Mir sind die Namen aller Studierenden nicht bekannt..daher bin ich mir in dem Punkt unsicher.
2.) Ich soll das Pumping Lemma auf folgende Sprache anwenden:
L={w Element von {0,1}*| |w|0 ungleich |w|1}
Soweit komme ich:
Ich wähle das Wort x = 0^N 1^N, somit ist mein Wort 2N, also >N.
x= 0r0s0t1N
Aufteilung des Wortes in uvw:
u = 0r,
v= 0s,
w= 0t,
und somit:
|r+s+t| = |N|
|s| >= 1
|rs| <= |N|
aber hier komme ich auch nicht mehr weiter.
Vielleicht hat ihr jemand ne Idee?
Vielen Dank
Euer Maxpayne0
|
|
| Thema: Regulärer Ausdruck & Äquivalenz rechtslineare Grammatik |
|
|
Genau hast recht, ich bräuchte in dem Fall jedoch mindestens einmal jedes Paar.
Um nochmal auf meine Frage zu kommen.
Auf einem der Folien unseres Dozenten steht:
ab | bc = die Sprache die das Wort ab UND bc enthält.
(ab)* | (bc)+ (gemeint ist ein hochgestelltes Plus) = die Sprache die beliebige Anzahl ab enthält ODER beliebige Anzahl bc (mindestens einmal).
Worin unterscheidet sich hier das UND und ODER?
Es leuchtet mir einfach nicht ein ...
Maxpayne0
|
|
| Thema: Regulärer Ausdruck & Äquivalenz rechtslineare Grammatik |
|
|
@as_string
Vielen Dank, klingt logisch!
Eine Frage hätte ich zu Ausdrücken noch.
Im Beispiel:
((101|001)|(01|10+))
heißt es ja auf der einen Seite (101|001) entweder oder,
auf der anderen Seite (01|10) kann zwischen 01 und 10 beliebig gewählt werden.
Wie ist das zu erklären?
@Karlito
Danke! Du hast vollkommen Recht, mir war bisher der Unterschied von Typ-3-Grammatiken und rechtslinearen Grammatiken nicht klar.
Ist es eigentlich jedes Mal erforderlich eine Typ-3-Grammatik in eine rechtslineare umzuwandeln, um einen endlichen Automaten zu konstruieren?
Das gäbe ja bei einigen Fällen ziemlich viele neue Zustände...
|
|
| Thema: Regulärer Ausdruck & Äquivalenz rechtslineare Grammatik |
|
|
Hi an alle,
ich sitze grad an einer Übung dran und bräucht etwas Hilfe.
1.)
Ich möchte einen regulären Ausdruck angeben, der folgende Sprache spricht:
Entweder 101 oder 001 oder eine beliebig viele Anzahl der Paare 01 und 10, wobei die Paare mindestens einmal vorkommen müssen (Reihenfolge der Paare ist beliebig).
Wäre der reguläre Ausdruck so richtig:
((101|001)|(01|10+))
2.)
Ich soll folgende Typ-3 Grammatik in eine äquivalente rechtslineare Grammatik transformieren:
G= ({a,b},{S,T,U},P,S)
P={S->abT,
S->aT,
T->bS,
T->b,
T->baU,
T->bU,
U->aS,
U->a,
U->epsilon}
Leider finde ich dazu nichts.
Wäre jemand eventuell so freundlich und würde mir die Vorgehensweise erklären?
Vielen Dank.
Euer Maypayne0
|
|
|
