Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » LR(0)-Grammatiken » Definition LR(0)-Grammatik
Begriffsdefinition: Reduktion LR(0)-Grammatiken Definition von Begriffen für eine verbale Definition von LR(0)-Grammatiken

Definition LR(0)-Grammatik

Sei $G=(V,\Sigma,P,S)$ eine kontextfreie Grammatik. $G$ heißt LR(0)-Grammatik falls für alle $z,z',z''\in \sigma^{*}$ $y,x,x'\in(\sigma\cup v)^{*}$ und $A,A'\in v$ gilt:

\begin{displaymath}\left.\begin{array}{l} S\Rightarrow_{R}^{*}xAz\Rightarrow_{R}... ...\ \end {array}\right\}\Rightarrow x=x',\,\,\,a=a',\,\,\,z'=z''\end{displaymath}

Weiterhin heißt $G$ nur LR(0)-Grammatik, wenn sie keine nutzlosen Variablen enthält und das Startsymbol niemals rechts steht. Zur Vereinfachung nehmen wir des weiteren an, daß unsere LR(0)-Grammatiken keine $\epsilon$-Regeln enthalten.
Begriffsdefinition: Reduktion LR(0)-Grammatiken Definition von Begriffen für eine verbale Definition von LR(0)-Grammatiken