Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Grammatiken » Definitionen bzgl. Grammatiken
Grammatiken Grammatiken Chomsky Hierarchie
Unterabschnitte

Definitionen bzgl. Grammatiken

Notation

Jeder Identifier besteht aus einem Buchstaben gefolgt von beliebig vielen Buchstaben oder Ziffern.
$\Leftrightarrow$
$L_{Idf}=L_{Buchstabe}\circ(L_{Buchstabe}\cup L_{Ziffer})^{*}$
$\Leftrightarrow$
Idf $\rightarrow$ Buchstabe|Buchstabe A
A $\rightarrow$ Buchstabe|Buchstabe A|Ziffer|Ziffer A
Buchstabe $\rightarrow$ ,,A''|,,B''|...|,,Z''|,,a''|...|,,z''
Ziffer $\rightarrow$ ,,0''|...|,,9''
Man kann die Ableitung eines Wortes mit Hilfe der Symbole $\Rightarrow$ und $\Rightarrow^{*}$ darstellen. Dabei steht
  • $\Rightarrow$ für die Anwendung von nur einer Regel und
  • $\Rightarrow^{*}$ für die Anwendung beliebig vieler Regeln.

Definition Grammatik

Eine Grammatik ist ein 4er-Tupel $G=(V,\Sigma,P,S)$ wobei
  • $V$: endliche Menge von Nichtterminalen44
  • $\Sigma$: endliche Menge von Terminalsymbolen. Dabei gilt $V\cap\Sigma=\emptyset$.
  • $P$: Produktions bzw. Regelsystem. Einzelne Teile des Systems heißen ,,Produktion'' oder ,,Regel''.
  • $S$: Das Startsymbol $(S\in V)$

Die durch eine Grammatik erzeugte Sprache

Die Sprache enthält alle durch die Grammatik G erzeugbaren Wörter:

\begin{displaymath}L(G)=\{w\in\Sigma^{*}:S\Rightarrow^{*}w\}\end{displaymath}

Äquivalenzen von Grammatiken

Zwei Grammatiken $G_{1}$ und $G_{2}$ heißen äquivalent, wenn sie dieselbe Sprache erzeugen:

\begin{displaymath}L(G_{1})=L(G_{2})\end{displaymath}


Fußnoten

... Nichtterminalen44
Nichtterminale kann man auch Variablen nennen.
Grammatiken Grammatiken Chomsky Hierarchie