LR(k)- Grammatik Nachweis < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Weisen Sie nach, ob die Spracke L = ( [mm] ab^{2n+1}c [/mm] | n [mm] \ge [/mm] 0) eine LR(k) Grammatik ist. |
Der Nachweis, ob eine Grammatik eine LR(k)- Grammatik ist, wird ja über die FIRST- Funktion geführt, d.h.
[mm] FIRST_{|P1|+|P1|+k}(P_1P_2P_3) [/mm] = [mm] FIRST_{|P1|+|P1|+k}(P_1'P_2'P_3')
[/mm]
Mir ist allerdings nicht klar, wie ich jetzt bestimme, welcher Teil des Terminalwortes jetzt [mm] P_1, P_2 [/mm] oder [mm] P_3 [/mm] entspricht... ich kann das doch wohl nicht so einfach völlig willkürlich festlegen, oder?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:09 Mi 17.11.2010 | | Autor: | felixf |
Moin!
> Weisen Sie nach, ob die Spracke L = ( [mm]ab^{2n+1}c[/mm] | n [mm]\ge[/mm] 0)
> eine LR(k) Grammatik ist.
Gemeint ist wohl eher, ob die Sprache eine LR(k)-Grammatik besitzt?
Man sieht jedoch sehr schnell, dass die Sprache sogar regulaer ist, z.B. mit Hilfe des regulaeren Ausdrucks $a [mm] (bb)^\ast [/mm] b c$. Und zu jeder Sprache gibt es natuerlich auch eine LR(k)-Grammatik.
> Der Nachweis, ob eine Grammatik eine LR(k)- Grammatik ist,
> wird ja über die FIRST- Funktion geführt, d.h.
> [mm]FIRST_{|P1|+|P1|+k}(P_1P_2P_3)[/mm] =
> [mm]FIRST_{|P1|+|P1|+k}(P_1'P_2'P_3')[/mm]
Das sagt mir grad nichts, allerdings hab ich das Zeugs auch schon seit Ewigkeiten nicht mehr genauer angeschaut 
Ich hoffe das oben hilft trotzdem weiter...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 05:14 Fr 19.11.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
