Kontextfreie Sprachen

Eine kontextfreie Sprache läßt sich mittels kontextfreie Grammatik und eines entsprechenden Kellerauotmaten (PDA) erzeugen. Eine deterministisch kontextfreie Sprache läßt sich mittels kontextfreie Grammatik und eines entsprechenden deterministischen Kellerauotmaten (DPDA) erzeugen.

Seien $ T\ ,A_{i} $ ein Nichtterminal und $ a_{i} $ ein Terminal, für i = 0 , ... , n , so gelten folgende Bildungsvorschriften:

$ T\ \rightarrow \{A_{i}\vert a_{i}\}^{*} $ und $ T\ \rightarrow \varepsilon $

Beispielsprache:

$ a^{m}b^{m}\ $

$ G_{1}=\ (V_{1},T,R_{1},S_{1}) $
$ G_{2}=\ (V_{2},T,R_{2},S_{2}) $

Vereinigung

$ G_{3}=G_{1}\cup G_{2} $
$ G_{3}=(V_{1}\cup V_{2}\cup \{S\},T,R_{1}\cup R_{2}\cup \{S\rightarrow S_{1},S_{2}\},S) $

Verknüpfung

$ G_{4}=G_{1}\circ G_{2} $
$ G_{4}=(V_{1}\cup V_{2},T,R_{1}\cup R_{2}\cup \{S\rightarrow S_{1}S_{2}\},S) $

Kleensche Hülle

$ G^{*}=(V_{1}\cup \{S\},T,R\cup \{S\rightarrow S_{1}S\mid \epsilon \ \},S) $