Thema: Grammatik für Sprache erstelllen |
|
Ich gehe davon aus, dass das Leere Wort ein Tippfehler ist (Epsilon statt Element), die Formulierung macht keinen Sinn.
Im Normalfall würde man schreiben . Also, das w ein Element aus Sigma ist und für w etwas besonderes gilt.
bedeutet eine beliebige Kombination aus 0 und 1, inklusive das leere Wort.
|
|
Thema: Grammatik für Sprache erstelllen |
|
So ganz verstehe ich das auch nicht, weil mich das Epsilon darin irritiert. Es könnte heißen. Das würde bedeuten, dass ein Wort w "10" an irgendeiner Stelle enthalten muss. Du müsstest also eine Grammatik entwerfen, die quasi ein Wort w = uvw erstellt, mit .
Gruß
3c7
|
|
Thema: Reguläre Sprache - Pumping Lemma |
|
Hi, ich hoffe das ist so verständlich:
Du kannst also auch abpumpen (i=0 setzen), was hier sinnvoller ist. So kannst du relativ schnell zeigen, dass die Sprache nicht regulär ist.
Gruß 3c7
|
|
Thema: Reguläre Sprache - Pumping Lemma |
|
Hallo zusammen,
hab gerade ein ähnliches Problem. Eine meiner Meinung nach reguläre Sprache L = {(a^k)^2 | k>=0} lässt sich mit Hilfe einer Typ 3 Grammatik G=({a}, {S,A} {S->e | aA, A-> aS}, S) erstellen. Beispiele für in L enthaltene Wörter wären also L = {e, aa, aaaa, aaaaaa, ...}.
Wende ich nun das Pumping Lemma auf L an, komme ich schlussendlich auf einen Widerspruch.
Ich habe mal versucht, mein Vorgehen aufzuschreiben:
Ich vermute, der Fehler liegt in der Schlussfolgerung, beziehe mich ja nur auf die Länge des Wortes. Kann mir da jemand helfen?
Viele Grüße
Edit:
Andere Überlegung. Nach dem Pumping Lemma liegt die Länge von x zwischen zwei Quadraten und daher gehört x nicht in die Sprache:
Andere Argumentation, gleiches Ergebnis. Da ist doch irgendwo ein gewaltiger Denkfehler drin...
Edit 2:
Zur Ursprungsthematik:
Ich gehe davon aus, das bei Sprachen mit endlicher Anzahl Wörter das Pumping Lemma nicht anwendbar ist. Wir haben bei uns in der Hochschule darüber gesprochen, dass die Variable für die Länge des gewählten Wortes - in diesem Fall n - quasi "unbekannt" ist. Man sagt nur, dass und ab der Länge des Wortes eine Zerlegung existiert.
|
|
|