Informatiker Board | formale Sprachen | Grammatik für Sprache erstelllen

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Grammatik für Sprache erstelllen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Grammatik für Sprache erstelllen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

Grammatik für Sprache erstelllen

Zitatantwort auf diesen Beitrag erstellen

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)

coooo hat dieses Bild (verkleinerte Version) angehängt:

05.02.2015 01:02

Nehmen Sie coooo in Ihre Freundesliste auf

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

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 11:17

3c7
Grünschnabel

Dabei seit: 01.02.2015
Beiträge: 4

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von 3c7: 05.02.2015 12:48.

05.02.2015 12:47

Nehmen Sie 3c7 in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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 14:06

Nehmen Sie Karlito in Ihre Freundesliste auf

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

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?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von coooo: 05.02.2015 17:58.

05.02.2015 17:54

3c7
Grünschnabel

Dabei seit: 01.02.2015
Beiträge: 4

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.

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von 3c7: 05.02.2015 20:26.

05.02.2015 20:15

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

05.02.2015 22:21

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Grammatik für Sprache erstelllen