Index

Wahlpflichtthemen

2. Formale Sprachen (4)


Reguläre Sprachen - Zusammenhang mit endlichen Automaten

Wir bilden nun die Definitionen der regulären Sprachen auf die endlichen Automaten ab.

  1. Æ: Von keinem der Zustände ist der Endzustand erreichbar.
  2. {l}: Anfangs und Endzustand stimmen überein: Lambda-Automat
  3. {a}: Automat für das Zeichen a mit sF als Endzustand.
  4.  
    1. {a} È {b}: Vom Anfangszustand geht jeweils eine Kante für a und b zum Endzustand bzw. zusammengefasst eine Kante mit "doppelter" Beschriftung (a|b). Es liegen also parallele Kanten vor: Automat für die Vereinigung
    2. {a}{b} = {ab}: Über a wird ein Zwischenzustand und danach über b der Endzustand erreicht. Hier liegt also eine Verkettung von Kanten vor: Automat für das Produkt
    3. {a}*: Kante zum gleichen Zustand sF: Automat für die Iteration
      Vergleicht man mit 2., so erkennt man, dass l enthalten ist.

 

[Index] [Zurück/Formale Sprachen 3] [Fortsetzung/Formale Sprachen 5 (Beispiele)]


Autor: Jürgen Dehmer
Letzte Änderung: