wilhelm büchner_728x90_bachelor_informatik
 

next up previous contents
Nächste Seite: Sprachen vom Typ 0 Aufwärts: Grammatiken Vorherige Seite: Transformation um die -Freiheit   Inhalt

Unterabschnitte

Abschlußeigenschaften

Ein Sprachtyp $i$ heißt $abgeschlossen$ unter $\bowtie$, falls für die Sprachen $L_{1}$ und $L_{2}$ vom Typ $i$ gilt:

\begin{displaymath}L_{1}\bowtie L_{2}\,ist\,auch\,vom\,Typ\, i\end{displaymath}

Vereinigung

Die Sprache $G_{\uplus}$ wird gebildet, indem man $G_{1}$ und $G_{2}$ vereinigt45 und ein neues Startsymbol einfügt, von welchem auf die Startsymbole von $G_{1}$ und $G_{2}$ gezeigt wird:

\begin{displaymath}S\rightarrow S_{1}\end{displaymath}


\begin{displaymath}S\rightarrow S_{2}\end{displaymath}

Die Sprache $L(G_{\uplus})$ enthält dann alle Wörter die die beiden Sprachen auch enthalten haben.

Konkatenation

Mit der Konkatenation ( $G_{1}\circ G_{2}$) werden die beiden Grammatiken hintereinandergeschaltet. Zuerst kommt ein Wort der Sprache $L(G_{1})$, dann eins der Sprache $L(G_{2})$. Dies erreicht man indem man ein neues Startsymbol $S$ einführt und für dieses folgende Regel definiert:

\begin{displaymath}S\rightarrow S_{1}S_{2}\end{displaymath}

Kleenabschluß

Beim Kleenabschluß ($G^{*}$) kommen beliebig viele Wörter der Grammatik G hintereinander46.

Fußnoten

... vereinigt45
$G_{1}\uplus G_{2}$
... hintereinander46
Klar, wie man das macht: $S'\rightarrow SS'$