Reguläre Sprachen: Unterschied zwischen den Versionen

Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen
 
(14 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 4: Zeile 4:
  
 
Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.
 
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:<br/>
 +
 +
<math> T \rightarrow aA </math> Rechtsrekursion, <br/>
 +
<math> T \rightarrow Aa </math> Linksrekursion, <br/>
 +
<math> A \rightarrow a </math>
 +
 +
Überführungsfunktion für einen DFA: <br/>
 +
 +
<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>
 +
 +
 +
<b>Abgeschlossen bzgl:</b>
 +
<ul>
 +
<li><math> \cup\ </math> Vereinigung</li>
 +
<li><math> \cap\ </math> Schnitt</li>
 +
<li><math> ^- </math>  Komplement</li>
 +
<li><math> \circ\ </math> Verknüpfung</li>
 +
<li><math> *\ </math> Sternhülle</li>
 +
</ul>
 +
 +
<b>Komplement</b>
 +
 +
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> <br/>
 +
 +
 +
 +
<b>Schnitt</b> <br/>
 +
 +
<math>M = ( Z\ , \Sigma , \delta , p_0 , E\ ) </math> <br/>
 +
<math>N = ( Z\ , \Sigma , \delta , q_0 , E\ ) </math> <br/>
 +
<math> M\ \bigcap N\ = ( \Z_M \times \Z_N , \Sigma , \delta^* , (p_0, q_0) , E_M\ \times E_N\ ) </math> <br/>
 +
 +
<math> \delta^*( ( p,q ), a )  = (  \delta_M (p,a),  \delta_N (q,a)  )\ </math>
 +
 +
<b>Vereinigung</b> <br/>
 +
 +
<math> M \bigcup N = \overline{ \overline{M\ } \bigcap \overline{N\ } }  </math> ( de Morgansche Regel ) <br/>
 +
 +
 +
<b>Verknüpfung</b> <br/>
 +
 +
<math> M \circ N = ( Z_1 \cup Z_2 , \Sigma , \delta , Q_1 , E ) </math>
 +
 +
<math> \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} </math>
 +
 +
<math>  E\ = \begin{cases}  E_1 \bigcup E_2 , Q_2 \bigcap E_2  \neq \emptyset  \\ E_2 , sonst \end{cases} </math> <br/>
 +
 +
<b>Kleensche Hülle </b>
 +
 +
<math> N^* = ( Z_1 \cup \{q_{neu}\} , \Sigma , \delta^* , Q_1 \cup \{q_{neu}\} , E_1 \cup \{q_{neu}\} ) </math><br/>
 +
<math> \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} </math> <br/>

Aktuelle Version vom 30. März 2008, 16:47 Uhr


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> ( de Morgansche Regel )


Verknüpfung

<math> M \circ N = ( Z_1 \cup Z_2 , \Sigma , \delta , Q_1 , E ) </math>

<math> \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} </math>

<math> E\ = \begin{cases} E_1 \bigcup E_2 , Q_2 \bigcap E_2 \neq \emptyset \\ E_2 , sonst \end{cases} </math>

Kleensche Hülle

<math> N^* = ( Z_1 \cup \{q_{neu}\} , \Sigma , \delta^* , Q_1 \cup \{q_{neu}\} , E_1 \cup \{q_{neu}\} ) </math>
<math> \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} </math>