Index

Wahlpflichtthemen

2. Formale Sprachen (7)


l-Automaten

Festlegung und Beispiele

Wie im vorherigen Abschnitt bereits erwähnt, heißen Automaten, welche l-Übergänge enthalten, auch l-Automaten (lEA).

Es sei E = {a,b,c}.

Lambda-Automat 1 Betrachten wir nebenstehenden Automaten, so stellen wir fest, dass die zugehörige Sprache aus Wörtern besteht, die zunächst beliebig viele a und danach beliebig viele b oder beliebig viele c aufweisen. Der reguläre Ausdruck lautet also:
a = a*(b* È c*).

Der Automat kann vereinfacht werden, so dass keine l-Übergänge auftreten:
Vereinfachter Automat

Es stellt sich die Frage, ob das immer funktioniert. Ohne diesen Satz nun zu beweisen gilt:

Zu jedem l-Automaten (lEA) gibt es einen nichtdeterministischen endlichen Automaten(NEA), der dieselbe Sprache erkennt, d.h. es ist L(lEA) = L(NEA).

Man kann also sagen, dass die l-Automaten zwar ein zusätzliches Hilfsmittel darstellen, das die Übertragung regulärer Ausdrücke in einen endlichen Automaten mitunter erleichtert, aber sie ermöglichen keine größere Mächtigkeit der zugehörigen Sprachen.

Das nachfolgende Verfahren zeigt, wie aus einem lEA ein NEA erzeugt werden kann:

  1. Übernehme zunächst alle Zustände des lEA
  2. Mache alle Zustände zu Endzuständen, die über beliebig viele l-Übergänge zu einem Endzustand führen.
    Oder: Für jeden Übergang der Form wird s' zu einem Endzustand.
  3. Trage für alle Übergänge der Form
    die einfachen Übergänge ein.
  4. Übertrage alle Übergänge der Form .
  5. Streiche alle nicht erreichbaren Zustände und die damit verbundenen Kanten.

An einem Beispiel soll das Verfahren angewandt werden.

Übungsaufgaben

 

[Index] [Zurück/Formale Sprachen 5] [Fortsetzung/Semi-Thue-Systeme]


Autor: Jürgen Dehmer
Letzte Änderung: