Reguläre Sprachen: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 25: | Zeile 25: | ||
<li><math> *\ </math> Sternhülle</li> | <li><math> *\ </math> Sternhülle</li> | ||
</ul> | </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> | |||
<b>Verknüpfung</b> | |||
Version vom 30. März 2008, 15:37 Uhr
Reguläre Sprache
Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.
Seien Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): T\ , A\
Nichtterminale
und sei Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): a\
ein Terminale, so gelten folgende Bildungsvorschriften:
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): T \rightarrow aA
Rechtsrekursion,
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): T \rightarrow Aa
Linksrekursion,
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): A \rightarrow a
Überführungsfunktion für einen DFA:
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): 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ürFehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \ i = 0, ... , n-1 \}
Abgeschlossen bzgl:
- Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \cup\ Vereinigung
- Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \cap\ Schnitt
- Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): ^- Komplement
- Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \circ\ Verknüpfung
- Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): *\ Sternhülle
Komplement
Bei einem Automat, der das Komplement akzeptiert, werden alle Nicht-Endzustände zu Endzuständen und umgekehrt.
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): M = ( Z\ , \Sigma , \delta, q_0 , Z\ \backslash E\ )
Schnitt
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): M = ( Z\ , \Sigma , \delta , p_0 , E\ )
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): N = ( Z\ , \Sigma , \delta , q_0 , E\ )
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): M\ \bigcap N\ = ( \Z_M \times \Z_N , \Sigma , \delta^* , (p_0, q_0) , E_M\ \times E_N\ )
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): \delta^*( ( p,q ), a ) = ( \delta_M (p,a), \delta_N (q,a) )\
Vereinigung
Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://api.formulasearchengine.com/v1/“:): M \bigcup N = \overline{ \overline{M\ } \bigcap \overline{N\ } }
Verknüpfung
