Kontextfreie Grammatiken < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:28 Do 22.01.2009 | | Autor: | mas |
| Aufgabe | Gegeben sind die Buchstaben a, b und c. Gesucht ist eine kontextfreie Grammatik die folgende Form haben soll:
[mm] a^n b^m [/mm] c^(n-m)
n und m sind ganze Zahlen
n und m sind größer oder gleich 0
n ist größer oder gleich m
Beispiele: aaabcc, aacc, aaaabbbb |
Ich bin auf der suche nach einem Lösungsansatz, der mir weiterhilft...
Was ich mir so dachte:
S (Start) -> aX | X
X -> b | c | E (End)
irgendwie hab ich aber keine Ahnung wie der richtige weg auch nur ansatzweise aussieht...mir ist schon klar, dass das so wie es oben steht blödsinn is...weil in dieser form auch etwa "aaaaabcbcb dastehen könnte...
danke schon mal für eure mühen,
lg mas
PS:
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:13 Fr 23.01.2009 | | Autor: | bazzzty |
> Gegeben sind die Buchstaben a, b und c. Gesucht ist eine
> kontextfreie Grammatik die folgende Form haben soll:
>
> [mm]a^n b^m c^(n-m)[/mm]
>
> n und m sind ganze Zahlen
> n und m sind größer oder gleich 0
> n ist größer oder gleich m
> Beispiele: aaabcc, aacc, aaaabbbb
> Ich bin auf der suche nach einem Lösungsansatz, der mir
> weiterhilft...
>
> Was ich mir so dachte:
>
> S (Start) -> aX | X
> X -> b | c | E (End)
> irgendwie hab ich aber keine Ahnung wie der richtige weg
> auch nur ansatzweise aussieht...mir ist schon klar, dass
> das so wie es oben steht blödsinn is...weil in dieser form
> auch etwa "aaaaabcbcb dastehen könnte...
Es ist ein bißchen schwer, einen guten Tipp zu geben, ohne alles zu verraten. Ich versuche es mal so:
Statt [mm]a^n b^m c^(n-m)[/mm] kann man auch [mm]a^{n+m} b^m c^n[/mm] schreiben, oder noch ein wenig suggestiver:
[mm]a^n a^m b^m c^n[/mm]. Jetzt ne Idee?
|
|
|
|
