Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 4 von 4 Treffern

Autor

Beitrag

Thema: Grammatik für Sprache erstelllen

3c7

Antworten:	6
Hits:	6.078

05.02.2015 20:15

Forum: formale Sprachen

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 $[latex]L = \{w \in \Sigma^* | \text{ - hier Bedingung für w einsetzen - }\}[/latex]$ . Also, das w ein Element aus Sigma ist und für w etwas besonderes gilt.

$[latex]\{0,1\}^*[/latex]$ bedeutet eine beliebige Kombination aus 0 und 1, inklusive das leere Wort.

Thema: Grammatik für Sprache erstelllen

3c7

Antworten:	6
Hits:	6.078

05.02.2015 12:47

Forum: formale Sprachen

So ganz verstehe ich das auch nicht, weil mich das Epsilon darin irritiert. Es könnte $[latex]L=\{w \in \Sigma^* | w \text{enthält} 10\}[/latex]$ 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 $[latex]u \in \Sigma^*, v=10, w \in \Sigma^*[/latex]$ .

Gruß
3c7

Thema: Reguläre Sprache - Pumping Lemma

3c7

Antworten:	9
Hits:	6.612

04.02.2015 16:42

Forum: formale Sprachen

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

3c7

Antworten:	9
Hits:	6.612

01.02.2015 13:36

Forum: formale Sprachen

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 $[latex]\exists n \in \mathbb N[/latex]$ und ab der Länge des Wortes $[latex]|x| \ge n[/latex]$ eine Zerlegung [latex]x=uvw[/latex]

existiert.

Zeige Beiträge 1 bis 4 von 4 Treffern