Grammatik für Sprache erstelllen

05.02.2015, 01:02

coooo

Grammatik für Sprache erstelllen

Hallo,

ich möchte eine Grammatik zur folgenden Sprache über dem Alphabet Summenzeichen {0,1} entwerfen.

So, wie ich es verstehe, sollen alle Wörter erlaubt sein, die beliebig viele 0 und 1 enthalten. Also auch gemischt. Z.B. 01010101, 1110000,10101.

Stimmt das soweit? Ich verstehe nicht, wie ich daraus eine Grammatik entwickeln kann. Mein Vorschlag ist folgender:

(0 ODER 1 ) * SCHNITTMENGE (0 ODER 1 ) *

Ist bestimmt falsch, oder? Da man nur 2 Durchlaufe herbekommt.

Weiterhin ist die Frage, ob es dafür eine Reguläre Grammatik für diese Sprache gibt.

PS Leider kann ich für Symbole den Editor nicht benutzen, da die Java-Anwendung blockiert wird (habe bereits die Sicherheitsstufe von "sehr hoch" auf "mittel" gesetzt)

05.02.2015, 11:17

Auf diesen Beitrag antworten »

coooo

Also ich versteh die "Sprache" (siehe Bild im Anhang) nicht.

Es ist Epsilon angegeben, d.h. das leere Wort wird aktzeptiert
Und eine beliebige Folge von 0 und 1.

Jedoch versteh ich (0,1)* nicht. Können die Nullen und Einsen vermischt werden?

0101 ?

05.02.2015, 12:47

Auf diesen Beitrag antworten »

3c7

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

05.02.2015, 14:06

Auf diesen Beitrag antworten »

Karlito

Ich denke es läuft auf jeden Fall darauf hinaus, dass L alle Wörter enthält, welche an irgendeiner stelle 10 enthalten. Die Grammatik dafür lässt sich leicht entweder direkt erstellen (durch Nachdenken) oder indem man vorher einen entsprechenden Automaten konstruiert.

Gruß,

Karlito

05.02.2015, 17:54

Auf diesen Beitrag antworten »

coooo

Zitat:

Original von Karlito
Ich denke es läuft auf jeden Fall darauf hinaus, dass L alle Wörter enthält, welche an irgendeiner stelle 10 enthalten. Die Grammatik dafür lässt sich leicht entweder direkt erstellen (durch Nachdenken) oder indem man vorher einen entsprechenden Automaten konstruiert.

Gruß,

Karlito

Danke. Und wozu dann das leere Wort? Also kann die Zeichenkette leer sein, oder 1 und 0 enthalten + mindestens 10 ?

Und Sigma Stern aus (0,1) bedeutet : Beliebige Zeichenkette aus Nullen und Einsen, oder?

05.02.2015, 20:15

Auf diesen Beitrag antworten »

3c7

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.

05.02.2015, 22:21

Auf diesen Beitrag antworten »

Karlito

Genau so würde ich das auch interpretieren. Was mich nur daran stört ist, dass ich es so formulieren würde:

$[latex]<br /> L = \{w | w \in \Sigma^* \wedge w \text{ enthält } 10\}<br /> [/latex]$

Aber in Mathe-Sprech bin ich nicht ganz so fit und habe jetzt auch nicht recherchiert....

Gruß,

Karlito

Neue Frage »

Antworten »

Grammatik für Sprache erstelllen

Verwandte Themen