regelsystem einer form.grammat < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:49 Fr 05.01.2007 | | Autor: | AriR |
hey leute, angenommen ich habe ein regelsystem in dem A eine Variable ist und a,b sind Elemente aus dem ihr zugrundeliegenden Alphabet und es exstiert die regel
A-->a
kann es dann noch vorkommen, dass eine regel auftaucht in
der zB A-->b gilt.
also ist Ableitung von A eindeutig bestimmt? in manchen beweisen kommt mir so vor, als ob man davon ausgeht, dass jede Variable auf einen konkreten wert nur gehen kann.
Ich hoffe ihr versteht was ich meine und könnte mir bitte weiterhelfen.
Gruß Ari :)
|
|
| |
|
Hallo,
das ist doch gerade der Witz an der Sache, dass es im Allgemeinen mehrere Produktionsregeln der Form [mm] $A\rightarrow [/mm] x$ für mehrere x geben kann. Für allgemeine Grammatiken kann man also nicht davon ausgehen, dass es zu einer Variablen (Nichtterminalsymbol) nur eine mögliche Produktionsregeln gibt.
Gruß
Martin
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:31 Fr 05.01.2007 | | Autor: | AriR |
eins verstehe ich nicht so ganz dann.
wenn man sich mal die Chomskynormalform anguckt bei wiki(http://de.wikipedia.org/wiki/Chomsky-Normalform)
dann steht da bei Schritt3, dass man bei regeln wie A-->B
die A durch B ersetzen soll in jeder Produktion. damit sind doch nur die A auf der rechten seite der Produktionen gemeint oder?
wenn man jetzt aber zB hast A-->B und A-->C. was macht man dann? ersetzt man die A durch B oder durch C?
das war auch eines der probleme, die ich unteranderem nicht verstanden habe :(
hoffe ihr könnt mir da nochmal weiterhelfen.
Gruß Ari
|
|
|
| |
|
Hallo,
ich finde, das ist in dem Artikel vielleicht etwas ungeschickt formuliert.
> wenn man jetzt aber zB hast A-->B und A-->C. was macht man dann? ersetzt man die A durch B oder durch C?
Durch beides! Dazu verdoppelt man einfach die zu verändernde Regel und ersetzt das A mal durch B und mal durch C.
Wir können das mal an einem kleinen Beispiel durchexerzieren:
[mm] $S\rightarrow [/mm] A$, [mm] $A\rightarrow [/mm] B$, [mm] $A\rightarrow [/mm] C$, [mm] $B\rightarrow [/mm] b$, [mm] $C\rightarrow [/mm] c$
Jetzt Schritt 1 aus der Wikipedia:
[mm] $S\rightarrow [/mm] A$, [mm] $A\rightarrow [/mm] B$, [mm] $A\rightarrow [/mm] C$, [mm] $B\rightarrow [/mm] X$, [mm] $C\rightarrow [/mm] Y$, [mm] $X\rightarrow [/mm] b$, [mm] $Y\rightarrow [/mm] c$
Schritt 2 ist überflüssig.
Schritt 3: Entfernen von [mm] $A\rightarrow [/mm] ...$
[mm] $S\rightarrow [/mm] B$, [mm] $S\rightarrow [/mm] C$, [mm] $B\rightarrow [/mm] X$, [mm] $C\rightarrow [/mm] Y$, [mm] $X\rightarrow [/mm] b$, [mm] $Y\rightarrow [/mm] c$
Entfernen von [mm] $B\rightarrow [/mm] ...$
[mm] $S\rightarrow [/mm] X$, [mm] $S\rightarrow [/mm] C$, [mm] $C\rightarrow [/mm] Y$, [mm] $X\rightarrow [/mm] b$, [mm] $Y\rightarrow [/mm] c$
Entfernen von [mm] $C\rightarrow [/mm] ...$
[mm] $S\rightarrow [/mm] X$, [mm] $S\rightarrow [/mm] Y$, [mm] $X\rightarrow [/mm] b$, [mm] $Y\rightarrow [/mm] c$
Fertig!
Gruß
Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:05 Fr 05.01.2007 | | Autor: | AriR |
jo danke jetzt hab ich es :)
gruß ari :)
|
|
|
|
