Reguläre Sprachen: Unterschied zwischen den Versionen
Aus Byte-Welt Wiki
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 5: | Zeile 5: | ||
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. | ||
Ü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> | <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> | ||
Version vom 25. März 2008, 03:43 Uhr
Reguläre Sprache
Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.
Ü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
