---

Geschrieben von lego am 19.11.2006 um 18:12:

  Grammatik zu Sprache finden

Hallo, habe ein Problem mit diser Aufgabe

Man gebe eine rechtlineare/linklineare Grammatik an, die L={a(ba)^n : n >= 0}

Meiner Meinung nach geht das gar nicht, denn die einzige Weise, wie ich den hinteren Teil eines solche Wortes erzeugen kann, ist mit einer Regel, die ca so aussieht:

S->bSa

aber das ist weder rechts noch linklinear oder täusche ich mich da?

---

Geschrieben von Abakus am 19.11.2006 um 18:39:

  RE: Grammatik zu Sprache finden

Ich versuche mich mal daran, wie ist folgendes:

S1 -> a S2

S2 -> # | b S3

S3 -> a | a S2

# steht dabei für das leere Wort.

Grüße Abakus

---

Geschrieben von lego am 19.11.2006 um 19:29:

 

hm, was mir gerade aufgefallen ist, nachdem ich versucht habe deinen Post nachzuvollziehen: (ab)^n heißt ja, dass ich wörter bilden soll, die so aussehen

aabababab..

und nicht, wie ich es im kopf hatte

aaaaabbbb

wenn ich keinen Gedankenfehler habe, dann wäre

S->aT
T->baT
T->#

rechtslineare Grammatik und

S->Tab
T->Tab
T->Va
V->#

linkslinar Grammatik oder nicht?

---

Geschrieben von Abakus am 19.11.2006 um 19:35:

 

Ja, wobei allerdings #-Produktionen nicht allzu beliebt sind. Meist wird versucht, ohne die auszukommen.

Ich bin jetzt bei:

S1 -> a | a S2

S2 -> b S1

Grüße Abakus

---

Geschrieben von lego am 19.11.2006 um 19:44:

 

auch schön, sehr ökonomisch

dann wäre das soweit geklärt, hätte aber noch eine andere frage, wenn du noch zeit und lust hättest:

zu zeigen: Die Sprache L={a^mb^n : m>=n} ist nicht regulär.

Hier fehlt mir der Ansatz, hab mir bei wiki nochmal durchgelesen, was eine reguläre Sprache ausmacht, finde aber keinen punkt wo ich ansetzen kann

---

Geschrieben von Abakus am 19.11.2006 um 23:12:

 

Die Idee bei solchen Sachen ist meist eine Version des "Pumping-Lemmas" zu benutzen.

Du nimmst an, es gibt eine Zerlegung wie dort angegeben und führst das dann zum Widerspruch.

Grüße Abakus

---

Geschrieben von lego am 20.11.2006 um 11:21:

 

ah, ja, das hatten wir schon, danke für den tipp, werde es versuchen, melde mich bei problemen nochmal

---

Geschrieben von Asgard am 09.12.2006 um 12:03:

 

Zitat:

Original von lego wenn ich keinen Gedankenfehler habe, dann wäre S->aT T->baT T-># rechtslineare Grammatik und S->Tab T->Tab T->Va V-># linkslinar Grammatik oder nicht?

Diese Produktionen würden weder zu einer rechts-, noch zu einer linkslinearen Grammatik gehören. Bei einer rechtslinearen Grammatik sind alle Produktionen von der Form A -> aB oder A -> # . Also fällt eine Produktion "T->baT" raus.

Zitat:

Original von Abakus Ja, wobei allerdings #-Produktionen nicht allzu beliebt sind. Meist wird versucht, ohne die auszukommen.

Im Grunde hast Du ja Recht, aber bei rechts- bzw. linkslinearen Grammatiken sind Epsilon-Produktionen per Definiton gewünscht

Eine linkslineare Grammatik wäre meines Erachtens:

S -> Ta
T -> Sb | #