Informatiker Board | formale Sprachen | kotextsensitive Grammatik für a^2^n

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » kotextsensitive Grammatik für a^2^n

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

kotextsensitive Grammatik für a^2^n

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

flamigo
unregistriert

kotextsensitive Grammatik für a^2^n

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Hallo zusammen,

kann mir jemand bei der folgenden Aufgabe weiterhelfen:

Geben Sie eine kontextsensitive Grammatik an, die die Sprache L = {a^2^n | n >= 0} erzeugt.

Meine Ideen:
Die erzeugten Wörter sind a, aa, aaaa = a^4 , a^8 usw.
Grammatik G = ({a}, N, S, P).
P = { S -> A | aa | a,
A -> ....

13.07.2016 21:29

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

S -> a | AaB
Aa -> C | AA
Ca -> aaC
CB -> B
B -> epsilon

Die Erklärung lasse ich bewusst weg - du musst ja auch noch was tun Augenzwinkern

__________________
Syntax Highlighting fürs Board (Link)

14.07.2016 07:15

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

flamigo
Grünschnabel

Dabei seit: 13.07.2016
Beiträge: 2

Danke für die Hilfe. Allerdings ist irgendwo ein Fehler.
S => AaB => CB => B => epsilon
oder
S => AaB => AAB => AA
mehr ist nicht möglich. Oder übersehe ich was?

Folgendes müsste aber stimmen:

S -> AB | a,
A -> CA | a,
Ca -> aaC,
CB -> BB, zwei B, damit es kontextsensitiv ist
B -> epsilon

zweiter Aufgabenteil war irgendeine Grammatik mit nur 4 Regeln zu finden.
S -> ASB | a,
Aa -> aaA,
AB -> epsilon

Richtig?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von flamigo: 14.07.2016 13:04.

14.07.2016 12:14

Nehmen Sie flamigo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Ja, meine Grammatik ist falsch.
Aa -> Ca | AAa - so sollte es passen.

Aber deine Ansätzen sehen auch gut aus, habe es eben durchgespielt.

__________________
Syntax Highlighting fürs Board (Link)

15.07.2016 11:32

flamigo
Grünschnabel

Dabei seit: 13.07.2016
Beiträge: 2

Alles klar, danke.

15.07.2016 18:13

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » kotextsensitive Grammatik für a^2^n