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 $T\ ,A\$ sind Nichtterminale
und sei $a\$ ein Terminale, so gelten folgende Bildungsvorschriften:

$T\rightarrow aA$ Rechtsrekursion,
$T\rightarrow Aa$ Linksrekursion,
$A\rightarrow a$

Ü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:

@@ Zeile 5: / Zeile 5: @@
 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/>
+Sei <math> T\ , A\  </math> sind Nichtterminale <br/>
-<math> T \rightarrow Ta </math> Linksrekursion, <br/>
+und sei <math> a\ </math> ein Terminale, so gelten folgende Bildungsvorschriften:<br/>
-<math> T \rightarrow a </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/>