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 aT </math> Rechtsrekursion, <br/>
 +
<math> T \rightarrow Ta </math> Linksrekursion, <br/>
 +
<math> T \rightarrow a </math>
  
 
Überführungsfunktion für einen DFA: <br/>
 
Überführungsfunktion für einen DFA: <br/>

Version vom 25. März 2008, 12:43 Uhr


Reguläre Sprache

Reguläre Sprachen, werden durch reguläre Grammatiken, reguläre Ausdrücke und endliche Automaten (DFA bzw. NFA) erzeugt.

<math> T \rightarrow aT </math> Rechtsrekursion,
<math> T \rightarrow Ta </math> Linksrekursion,
<math> T \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