Reguläre Sprachen

Reguläre Sprache

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

Seien $ T\ ,A\ $ Nichtterminale und sei $ a\ $ ein Terminale, so gelten folgende Bildungsvorschriften:

$ T\rightarrow aA $ Rechtsrekursion,
$ T\rightarrow Aa $ Linksrekursion,
$ A\rightarrow a $

Überführungsfunktion für einen DFA:

$ L(M)=\{x_{1}...x_{n}\in {\Sigma ^{*}}\vert \exists q_{1}...q_{n-1}\in Z,q_{n}\in E\ :\delta (q_{i},x_{i+1})=q_{i+1} $ für$ \ i=0,...,n-1\} $

Abgeschlossen bzgl:

• $ \cup \ $ Vereinigung
• $ \cap \ $ Schnitt
• $ ^{-} $ Komplement
• $ \circ \ $ Verknüpfung
• $ *\ $ Sternhülle

Komplement

Bei einem Automat, der das Komplement akzeptiert, werden alle Nicht-Endzustände zu Endzuständen und umgekehrt.

$ M=(Z\ ,\Sigma ,\delta ,q_{0},Z\ \backslash E\ ) $

Schnitt

$ M=(Z\ ,\Sigma ,\delta ,p_{0},E\ ) $
$ N=(Z\ ,\Sigma ,\delta ,q_{0},E\ ) $
$ M\ \bigcap N\ =(\mathbb {Z} _{M}\times \mathbb {Z} _{N},\Sigma ,\delta ^{*},(p_{0},q_{0}),E_{M}\ \times E_{N}\ ) $

$ \delta ^{*}((p,q),a)=(\delta _{M}(p,a),\delta _{N}(q,a))\ $

Vereinigung

$ M\bigcup N={\overline {{\overline {M\ }}\bigcap {\overline {N\ }}}} $ ( de Morgansche Regel )

Verknüpfung

$ M\circ N=(Z_{1}\cup Z_{2},\Sigma ,\delta ,Q_{1},E) $

$ \delta (p,a)={\begin{cases}\delta _{M}(p,a),p\in Z_{1}\backslash E_{1}\\\delta _{M}(p,a)\cup \bigcup _{q\in Q_{2}}\delta _{N}(q,a),p\in E_{1}\\\delta _{N}(p,a),sonst\end{cases}} $

$ E\ ={\begin{cases}E_{1}\bigcup E_{2},Q_{2}\bigcap E_{2}\neq \emptyset \\E_{2},sonst\end{cases}} $

Kleensche Hülle

$ N^{*}=(Z_{1}\cup \{q_{neu}\},\Sigma ,\delta ^{*},Q_{1}\cup \{q_{neu}\},E_{1}\cup \{q_{neu}\}) $
$ \delta ^{*}(p,a)={\begin{cases}\delta (p,a)\cup \bigcup _{q\in Q}\delta (q,a),p\in E_{1}\\\delta (p,a),sonst\end{cases}} $