| Die letzten 8 Beiträge |
| 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 
Eine linkslineare Grammatik wäre meines Erachtens:
S -> Ta
T -> Sb | # |
| lego |
ah, ja, das hatten wir schon, danke für den tipp, werde es versuchen, melde mich bei problemen nochmal 
|
| 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
|
| 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 |
| 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
|
| 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? 
|
| 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
|
| 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? |
|
|
