Anzahl von b's durch 3 teilbar < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:07 So 07.04.2013 | | Autor: | bandchef |
| Aufgabe | | Konstruieren Sie für die folgende Sprache jeweils eine reguläre Grammatik über [mm] $\Sigma=\{a,b\}$: $L_3 [/mm] = [mm] \{w \in \Sigma^{\star} | \text{ Die Anzahl der b's in w ist durch 3 teilbar}\}$ [/mm] |
Hi Leute!
Ich hab ein Problem zu dieser Sprach ein korrekte reguläre Grammatik zu entwerfen! Ich hab mir natürlich zu den Produktionen schon Gedanken gemacht, aber so richtig vorwärts gekommen bin ich noch nicht. Mein bisheriges Ergebnis:
S->aA, S->bB, B->eps, A->eps, A->aA, A->bB, B->bB, B->aA
So wie die Produktionen momentan sind, erstellt es mir ein jedes mögliches Wort aus a,b; die kleene'sche Hülle quasi.
Das Problem was ich nun hier habe, ist, dass ich ja irgendwie einen Zähler bräuchte, der mir mitzählt, wann ich entweder 0, 6, 9, 12, oder, oder, oder b's (eben eine Anzahl die gerade durch 3 teilbar ist) im Wort w habe.
Aber wie mache ich das jetzt nun???
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:49 Mo 08.04.2013 | | Autor: | sandp |
hi,
du brauchst mehr Nichtterminal-Symbole und denk mal über eine etwas größere Schleife nach.
Gruß
sandp
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:38 Mo 08.04.2013 | | Autor: | bandchef |
Ok. Ich hab gleich mal auf dich gehört!
Ich hab jetzt folgende Produktionen:
S->aA, S->bB, B->eps, A->eps, A->aA, B->bB, B->aA, A->bB, B->bC, C->bB
Mit dem Nichtterminal C kann ich nun sicherstellen, dass immer genau 3 b's erstellt werden. Problem an der Geschichte ist, dass diese 3 b's dann immer genau nacheinander kommen. Ich denke, die Grammatik soll aber doch flexibel genug sein, um 3,6,9,... nicht nur genau hintereinander erzeugen zu können, oder?
Kannst du mir nochmal drauf helfen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:02 Di 09.04.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Ich hab jetzt folgende Produktionen:
>
> S->aA, S->bB, B->eps, A->eps, A->aA, B->bB, B->aA, A->bB,
> B->bC, C->bB
>
> Mit dem Nichtterminal C kann ich nun sicherstellen, dass
> immer genau 3 b's erstellt werden.
Nein, das hast du nicht sichergestellt. Eine mögliche Ableitung bei deinen Produktionen wäre z.B. [mm] $S\to bB\to b\varepsilon=b$.
[/mm]
Vorschlag: Verwende Nichtterminale S (Startsymbol), T und U mit folgenden Bedeutungen:
S: bisher "durch 3 teilbare Anzahl" b's abgeleitet
T: bisher "durch 3 teilbare Anzahl + 1" b's abgeleitet
U: bisher "durch 3 teilbare Anzahl + 2" b's abgeleitet
Hilft dir das weiter?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:17 Di 09.04.2013 | | Autor: | bandchef |
Hi!
Erstmal danke für deine Antwort!
Ich hab zwar jetzt nicht deine NIchtterminal verwendet, aber ich denke, ich hab jetzt vielleicht doch eine Lösung gefunden die passt!
S->eps, S->aA, S->bB,
A->eps, A->aA, A->bB,
B->bC, B->aC
C->aC, C->bD,
D->aD, D->bE
E->eps, E->aA, E->bB,
So sollte es dann passen. Beispiel:
S->bB->baC->baaC->baaaC->baaaaC->baaaabD->baaaabaD->baaaababE->baaaabab
Passt das nun soweit?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:38 Di 09.04.2013 | | Autor: | tobit09 |
> S->eps, S->aA, S->bB,
> A->eps, A->aA, A->bB,
> C->aC, C->bD,
> D->aD, D->bE
> E->eps, E->aA, E->bB,
Bevor ich darauf antworte: Du hast vermutlich die Zeile mit den Ableitungen von B aus vergessen, oder? Falls ja: Kannst du sie bitte erst noch ergänzen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:42 Di 09.04.2013 | | Autor: | bandchef |
Oh. Sorry. Natürlich:
S->eps, S->aA, S->bB,
A->eps, A->aA, A->bB,
B->bC, B->aC
C->aC, C->bD,
D->aD, D->bE
E->eps, E->aA, E->bB,
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:59 Di 09.04.2013 | | Autor: | tobit09 |
> S->eps, S->aA, S->bB,
> A->eps, A->aA, A->bB,
> B->bC, B->aC
> C->aC, C->bD,
> D->aD, D->bE
> E->eps, E->aA, E->bB,
>
> So sollte es dann passen. Beispiel:
>
> S->bB->baC->baaC->baaaC->baaaaC->baaaabD->baaaabaD->baaaababE->baaaabab
>
> Passt das nun soweit?
Fast. Wenn du die Regel B->bC durch B->C ersetzt, passt es.
EDIT: Mir fällt gerade auf, dass die Grammatik dann ja nicht mehr regulär ist. Also geht das so auch nicht.
Sonst wäre z.B. auch
S->bB->bbC->bbbD->bbbbE->bbbb
eine mögliche Ableitung.
Ich denke, gerade bei so komplizierten Grammatiken ist es wichtig, sich zu überlegen, was die einzelnen Nichtterminale bedeuten sollen. Sonst verliert man den Überblick.
In deiner Version der Grammatik (mit der einen Korrektur von mir) stehen S und E für Wörter mit einer durch 3 teilbaren Anzahl von b's, B und C für Wörter mit "durch 3 teilbare Anzahl + 2" b's und D für Wörter mit "durch 3 teilbare Anzahl + 1" b's.
Man könnte die Grammatik vereinfachen, indem man alle E's durch S's und alle B's durch C's ersetzt.
EDIT: Unfug von mir.
EDIT: Folgende Vereinfachung tut es:
[mm] S->$\varepsilon$, [/mm] S->aS, S->bB
B->aB, B->bD
D->aD, D->bS
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:26 Di 09.04.2013 | | Autor: | bandchef |
Jetzt hast du mich rausgekickt 
Was muss ich nun an meiner Grammatik ändern, dass es passt? Du sprichst von einer Veränderung, die du gemacht hast. Die Veränderung, dass ich B->bC mit B->C ersetzen soll, geht ja gar nicht, weil sie eben dann nicht mehr regulär ist.
Mit deiner vereinfachten Grammatik kann man ein b zu viel bekommen:
S->bB->bbD->bbbS->bbbbB
Müsste es nicht so heißen:
S->, S->aS, S->bB
B->aB, B->bD
D->aD, D->aS
Edit: NEIN! DU hast natürlich RECHT. Ich hab vergessen, dass natürlich auch 6b's hintereinander kommen dürfen...; es können natürlich auch 4b's x mal a's und dann müssen noch zwei weitere b's kommen evtl. wieder getrennt von a's. Oder auch nicht. Das stellen die Produktionen natürlich alles sicher!
Danke für deine Hilfe!
|
|
|
|
