 Grammatik zu Sprache finden |
lego
Jungspund
Dabei seit: 19.11.2006
Beiträge: 11
 |
|
| 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?
|
|
19.11.2006 18:12 |
|
|
Abakus 
Grünschnabel
Dabei seit: 26.09.2006
Beiträge: 3
Herkunft: Niedersachsen
|
|
| 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 
|
|
|
19.11.2006 18:39 |
|
|
lego
Jungspund
Dabei seit: 19.11.2006
Beiträge: 11
|
|
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? 
|
|
|
19.11.2006 19:29 |
|
|
Abakus
Grünschnabel
Dabei seit: 26.09.2006
Beiträge: 3
Herkunft: Niedersachsen
|
|
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
|
|
|
19.11.2006 19:35 |
|
|
lego
Jungspund
Dabei seit: 19.11.2006
Beiträge: 11
|
|
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
|
|
|
19.11.2006 19:44 |
|
|
Abakus
Grünschnabel
Dabei seit: 26.09.2006
Beiträge: 3
Herkunft: Niedersachsen
|
|
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
|
|
|
19.11.2006 23:12 |
|
|
lego
Jungspund
Dabei seit: 19.11.2006
Beiträge: 11
|
|
ah, ja, das hatten wir schon, danke für den tipp, werde es versuchen, melde mich bei problemen nochmal
|
|
|
20.11.2006 11:21 |
|
|
|
