Informatiker Board | Theoretische Informatik

Informatiker Board » Themengebiete » Theoretische Informatik » Typ 1 Grammatik angeben

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Typ 1 Grammatik angeben

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Typ 1 Grammatik angeben

Zitatantwort auf diesen Beitrag erstellen

Hallo,
habe ein Problem ich möchte zu L={a^i b^j c^k | i,j,k >= 1 und (2i=j und 2j=k)}

eine Grammatik vom Typ 1 (kontextsensitiv) angeben, die die Sprache L erzeugt.

Ich versuch dies mit Abbildungen finde aber nix wegen der abhängigkeit von einander.

Also für a^n b^2n

a^n b^2n kriege ich das noch hin durch
S-> aSbb |abb

Aber mir fällt nix für
a^n b^2n c^4n ein .

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Pampelmuse: 27.05.2007 16:09.

27.05.2007 16:08

Nehmen Sie Pampelmuse in Ihre Freundesliste auf

kiste
Mitglied

Dabei seit: 06.05.2007
Beiträge: 29

Mhh wie wärs mit

S-> aSbbC |abbcccc
Cb -> bC
Cc -> cC
cC -> ccccc

29.05.2007 19:41

Nehmen Sie kiste in Ihre Freundesliste auf

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

S-> aSbbC |abbcccc
so läßt sich doch
aabbccccbbC erstellen dies ist aber nicht in der Sprache.
Werde die Lösung der Übungsgruppe demnächst hier präsentieren.

01.06.2007 11:33

qwertz
Grünschnabel

Dabei seit: 01.06.2007
Beiträge: 4

Bei solchen Sprachen empfiehlt sich immer die Verwendung von Läufervariablen (hier: Y,Z).

Folgende Grammatik müsste funktionieren:

S -> abbcccc | aXbbcccc

Xb -> bY

Yb -> bY

Yc -> Zbbccccc

bZ -> Zb

aZ -> aa | aaX

Ich hatte keine Zeit das ausführlich zu testen, aber bis i=3 funktioniert sie, also gehe ich mal davon aus, dass sie auch für i>3 geht.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von qwertz: 01.06.2007 14:55.

01.06.2007 14:54

Nehmen Sie qwertz in Ihre Freundesliste auf

Pampelmuse
Mitglied

Dabei seit: 12.04.2007
Beiträge: 32

Passt alles ganz gut.
Das ist der Hammer wäre überhaupt nicht darauf gekommen , nicht schlecht danke für den Beitrag.

03.06.2007 11:39

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Typ 1 Grammatik angeben