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\ }}}} $
Verknüpfung
