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 <math> T\ , A\ </math> Nichtterminale
und sei <math> a\ </math> ein Terminale, so gelten folgende Bildungsvorschriften:
<math> T \rightarrow aA </math> Rechtsrekursion,
<math> T \rightarrow Aa </math> Linksrekursion,
<math> A \rightarrow a </math>
Überführungsfunktion für einen DFA:
<math>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} </math> für<math>\ i = 0, ... , n-1 \} </math>
Abgeschlossen bzgl:
- <math> \cup\ </math> Vereinigung
- <math> \cap\ </math> Schnitt
- <math> ^- </math> Komplement
- <math> \circ\ </math> Verknüpfung
- <math> *\ </math> Sternhülle
Komplement
Bei einem Automat, der das Komplement akzeptiert, werden alle Nicht-Endzustände zu Endzuständen und umgekehrt.
<math> M = ( Z\ , \Sigma , \delta, q_0 , Z\ \backslash E\ ) </math>
Schnitt
<math>M = ( Z\ , \Sigma , \delta , p_0 , E\ ) </math>
<math>N = ( Z\ , \Sigma , \delta , q_0 , E\ ) </math>
<math> M\ \bigcap N\ = ( \Z_M \times \Z_N , \Sigma , \delta^* , (p_0, q_0) , E_M\ \times E_N\ ) </math>
<math> \delta^*( ( p,q ), a ) = ( \delta_M (p,a), \delta_N (q,a) )\ </math>
Vereinigung
<math> M \bigcup N = \overline{ \overline{M\ } \bigcap \overline{N\ } } </math>
Verknüpfung
