Kontextfreie Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Aufgabe | Gegeben sei die folgende kontextfreie Sprache:
L := [mm] \{w \in \{1\}^\* \{0\}^\* \{d\}^\* | \mbox{ |w|_1 + |w|_2 = 4*|w|_d}\}
[/mm]
Dabei bezeichnet [mm] |w|_{x} [/mm] die Anzahl der Vorkommnisse von x in w.
Entwerfen sie eine kontextfreie Grammitik G für L.
Geben sie eine Begründung für die Korrektheit ihrer Konstruktion an. |
Hallo :)
Wenn ich diese Aufgabe richtig verstehe kommen immer auf zwei Einsen und zwei Nullen ein d, denn 2+2 = 4*1
Nun ist mein Problem wie ich das in die Grammatik rein bekomme?
Kann mir hier bitte jemand helfen?
Danke :)
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 21:02 So 24.06.2007 | Autor: | Bastiane |
Hallo informatikmaus!
> Gegeben sei die folgende kontextfreie Sprache:
>
>
> L := [mm]\{w \in \{1\}^\* \{0\}^\* \{d\}^\* | \mbox{ |w|_1 + |w|_2 = 4*|w|_d}\}[/mm]
>
> Dabei bezeichnet [mm]|w|_{x}[/mm] die Anzahl der Vorkommnisse von x
> in w.
>
> Entwerfen sie eine kontextfreie Grammitik G für L.
> Geben sie eine Begründung für die Korrektheit ihrer
> Konstruktion an.
> Hallo :)
>
> Wenn ich diese Aufgabe richtig verstehe kommen immer auf
> zwei Einsen und zwei Nullen ein d, denn 2+2 = 4*1
Ist es nicht eher so, dass auf insgesamt 4 (Einsen oder Nullen) genau ein d kommt!? Könnte man für die Sprache nicht einfach alle Möglichkeiten, vier Einsen oder Nullen zu nehmen, aufzählen, und dazu jeweils ein d? Oder ist das dann nicht kontextfrei?
Viele Grüße
Bastiane
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 20:25 Di 26.06.2007 | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|