 Pumping Lemma & Beweis für reguläre Sprache |
Maxpayne0
Grünschnabel
Dabei seit: 31.10.2017
Beiträge: 5
 |
|
| 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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Maxpayne0: 12.11.2017 16:35.
|
|
12.11.2017 16:35 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo Maxpayne0,
zu 1.)
Ich denke deine Grammatik könnte bereits reichen. Hier noch eine andere Variante:
Es ist egal, ob Du die Menge der Namen der Studenten kennst. Es handelt sich um eine Menge von Wörtern. Für jedes Wort kann ein endlicher Automat angegeben werden und damit ist jedes Wort regulär. Da die regulären Sprachen unter Vereinigung abgeschlossen sind und die Menge der Namen endlich ist, gibt es eine Sprache, welche aus den Namen aller Studenten besteht.
zu 2.)
Leider bin ich mit dem Pumping-Lemma nicht so fit und kann dir deswegen momentan noch nicht helfen.
Besten Gruß,
Karlito
|
|
|
13.11.2017 07:39 |
|
|
|
