Grammatik zu Sprache finden |
19.11.2006, 18:12 | 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? |
||||
|
|||||
19.11.2006, 18:39 | 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 |
||||
19.11.2006, 19:29 | 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? |
||||
19.11.2006, 19:35 | 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 |
||||
Anzeige | |||||
|
|||||
19.11.2006, 19:44 | 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 |
||||
19.11.2006, 23:12 | 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 |
||||
20.11.2006, 11:21 | Auf diesen Beitrag antworten » | ||||
lego | ah, ja, das hatten wir schon, danke für den tipp, werde es versuchen, melde mich bei problemen nochmal |
||||
09.12.2006, 12:03 | Auf diesen Beitrag antworten » | ||||
Asgard |
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.
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 | # |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|