Grammatik zu Sprache finden

Neue Frage »

Auf diesen Beitrag antworten »
lego 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?
 
Auf diesen Beitrag antworten »
Abakus 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 smile
Auf diesen Beitrag antworten »
lego

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? Zunge raus
Auf diesen Beitrag antworten »
Abakus

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 smile
 
Auf diesen Beitrag antworten »
lego

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
Auf diesen Beitrag antworten »
Abakus

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 smile
Auf diesen Beitrag antworten »
lego

ah, ja, das hatten wir schon, danke für den tipp, werde es versuchen, melde mich bei problemen nochmal smile
Auf diesen Beitrag antworten »
Asgard

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 Augenzwinkern

Eine linkslineare Grammatik wäre meines Erachtens:

S -> Ta
T -> Sb | #
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »