Pumping Lemma & Beweis für reguläre Sprache |
| 12.11.2017, 16:35 | Auf diesen Beitrag antworten » |
| Maxpayne0 | 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 |
|
|
|
| 13.11.2017, 07:39 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
