Informatiker Board | formale Sprachen | Kontextfreie Grammatik

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Kontextfreie Grammatik

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Kontextfreie Grammatik

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

Kontextfreie Grammatik

Zitatantwort auf diesen Beitrag erstellen

Hallo,

habe unten die Aufgabenstellung. Es geht darum, eine Grammatik für die Sprache:

wabawr zu entwerfen.

Wie gehe ich hier vor? Die Grammatik soll kontextfrei sein, jedoch steht "W" links und "Wr"rechts vom festen String "aba"

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

10.05.2015 23:44

Nehmen Sie coooo in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Kontextfrei heißt doch nur, dass auf der linken Seite der Produktionen nur einzelne Nichtterminale stehen dürfen. Auf der rechten Seite kann so gut wie alles stehen. $[latex] S \rightarrow xSy [/latex]$ geht also. Das ist dein Handwerkszeug.

Gruß,

Karlito

11.05.2015 00:02

Nehmen Sie Karlito in Ihre Freundesliste auf

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

Danke.

Als nächstes habe ich: S---> aba

11.05.2015 21:24

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Das ist gut. Damit hast Du den Abschluss. Nun Fehlen die Produktionen, die [latex]w[/latex]

und

erzeugen. Folgende Grammatik (nur Produktionen angegeben) erzeugt die Sprache $[latex]\mathcal{L} = \{a^nb^n~|~n\in \mathbb{N}\}[/latex]$ :

$[latex] S & \rightarrow & \varepsilon S & \rightarrow & aSb [/latex]$

Gibt dir das den entscheidenden Hinweis?

Gruß,

Karlito

11.05.2015 23:15

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

Hm, ich weiß nicht so recht.

Würde die Aufgabe so lösen:

S ---> xSy

S ---> aba

S---> aSb

x---> AB

y ---> BA

A--- > a | e

B ---> b | e

11.05.2015 23:43

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Viel einfacher!

$[latex] S & \rightarrow & aba S & \rightarrow & aSa S & \rightarrow & bSb [/latex]$

Verstehst Du es?

Gruß,

Karlito

11.05.2015 23:51

coooo
Jungspund

Dabei seit: 01.02.2015
Beiträge: 22

Verstehe ich es richtig, dass ich S---> aba nur zum Schluss benutzen kann? da dort kein S enthalten ist?

12.05.2015 00:01

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Ja, somit wird die "Reihe" der Produktionen terminiert, da es kein weiteres Nichtterminal gibt,.

12.05.2015 00:14

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Kontextfreie Grammatik