---

Geschrieben von Maxpayne0 am 12.11.2017 um 16:35:

  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

---

Geschrieben von Karlito am 13.11.2017 um 07:39:

 

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