Reguläre Sprachen: Unterschied zwischen den Versionen
Aus Byte-Welt Wiki
Zur Navigation springenZur Suche springen| 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. | ||
| − | <math> T \rightarrow | + | Sei <math> T\ , A\ </math> sind Nichtterminale <br/> |
| − | <math> T \rightarrow | + | und sei <math> a\ </math> ein Terminale, so gelten folgende Bildungsvorschriften:<br/> |
| − | <math> | + | |
| + | <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/> | Überführungsfunktion für einen DFA: <br/> | ||
Version vom 25. März 2008, 12:45 Uhr
Reguläre Sprache
Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.
Sei <math> T\ , A\ </math> sind 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
