formale Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 10:23 Mi 03.04.2013 | | Autor: | bandchef |
| Aufgabe | Entwerfen sie eine Grammatik, die die folgende Sprache erzeugt:
[mm] $L=\{w|w\in\{3,5,7\}^{*}, w\text{ enthält die Ziffern 3, 5 und 7 gleich oft}\} [/mm] |
Hi Leute!
Ich brüte hier nun schon einige Tage über dieser Aufgabe und komme einfach nicht weiter!
Ich hab schon einige Regeln aufgestellt, eine Grammatik zu finden, die zu dieser Sprache passt, aber ich finde nix richtiges. Vielleicht könnt ihr mir ja helfen? Meine bisherigen Regeln:
[mm] $G=\{V, \sum, P, S\}$, $\sum=\{3,5,7\}$, $V=\{S,A,B,C\}$
[/mm]
und nun die Produktionen: [mm] $P=\{S->SA; S->AS; S->SBC; S->BSC; S->SCB; S->CSB; S->A; S->\epsilon; A->3; B->5; C->7\}$
[/mm]
Das geht aber auch nicht. Siehe dieses Beispiel: S->BSC->BBSCC->???
Solche könnte ich nun haufenweise anführen! Was ich noch dazu sagen möchte, ist, dass wir in der Vorlesung noch keine Chomsky-Hierarchien durchgenommen haben! Ich weiß also nicht in welchen Typ die Grammatiken die wir erstellen soll eingeordnet werden können! Ich denke, dass das momentan noch absichtlich beiseite gestellt worden um ein "Gefühl" für Grammatiken zu bekommen!
Ich hoffe ihr könnt mir hier weiterhelfen!
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:36 Mi 03.04.2013 | | Autor: | bandchef |
Noch ein weiterer Versuch:
$P={
[mm] S->\epsilon, [/mm]
S->SABC, S->ASBC, S->ABSC, S->ABCS,
S->SACB, S->ASCB, S->ACSB, S->ACBS,
S->SCAB, S->CSAB, S->CASB, S->CABS,
S->SCBA, S->CSBA, S->CBSA, S->CBAS,
S->SBCA, S->BSCA, S->BCSA, S->BCAS,
S->SBAC, S->BSAC, S->BASC, S->BACS,
A->3, B->5, C->7
}$
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:57 Mi 03.04.2013 | | Autor: | felixf |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Moin!
> Noch ein weiterer Versuch:
>
> $P={
> [mm]S->\epsilon,[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> S->SABC, S->ASBC, S->ABSC, S->ABCS,
> S->SACB, S->ASCB, S->ACSB, S->ACBS,
> S->SCAB, S->CSAB, S->CASB, S->CABS,
> S->SCBA, S->CSBA, S->CBSA, S->CBAS,
> S->SBCA, S->BSCA, S->BCSA, S->BCAS,
> S->SBAC, S->BSAC, S->BASC, S->BACS,
> A->3, B->5, C->7
> }$
Der Ansatz ist schonmal gut. Aber: warum so kompliziert?
Fang doch mit den Regeln $S \to \epsilon$, $S \to SABC$ an, und $A \to 3$, $B \to 5$, $C \to 7$ ist ebenfalls gut. Daneben brauchst du doch nur noch Regeln, die A mit B, A mit C, und B mit C vertauschen.
Das ist zwar eine sehr allgemeine Grammatik (vermutlich viel allgemeiner als noetig), da auf der linken Seite mehr als ein Nichtterminal stehen kann, aber sie funktioniert.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:09 Mi 03.04.2013 | | Autor: | bandchef |
Manchmal sehe ich den Wald vor lauter Bäumen nicht! So einfach kann's sein. Ich hab jetzt folgende Grammatik entworfen:
[mm] $G=\{V, \sum, P, S\}$, $\sum=\{3,5,7\}$, $V=\{S, A, B, C\}$
[/mm]
[mm] $P=\{S\to\epsilon, S\to SABC, A\to B, B\to C, A\to C, A\to 3, B\to 5, C\to 7\}$
[/mm]
Aber fehlen da nicht jetzt nicht noch die Vertauschungen: B->A, C->A und C->B? Oder sind die überflüssig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:25 Mi 03.04.2013 | | Autor: | felixf |
Moin!
Sorry, ich glaub ich hatte mich etwas ungenau ausgedrueckt. Mit tauschen meine ich, dass man AB durch BA, AC durch CA und BC durch CB ersetzen kann.
> Manchmal sehe ich den Wald vor lauter Bäumen nicht! So
> einfach kann's sein. Ich hab jetzt folgende Grammatik
> entworfen:
>
> [mm]G=\{V, \sum, P, S\}[/mm], [mm]\sum=\{3,5,7\}[/mm], [mm]V=\{S, A, B, C\}[/mm]
>
> [mm]P=\{S\to\epsilon, S\to SABC, A\to B, B\to C, A\to C, A\to 3, B\to 5, C\to 7\}[/mm]
Hier kann man z.B. das Wort AAB mit erzeugen, was nicht in der Sprache liegt.
LG Felix
|
|
|
|
