Lemma von Arden

Lemma von Arden

Das Lemma von Arden trifft eine Aussage über Mengen von Zeichenreihen, welche im Rahmen der formalen Sprachen Gegenstand der theoretischen Informatik, spezieller der Automatentheorie sind.

Inhaltsverzeichnis

Formulierung

Es sei Σ eine beliebiges Alphabet; * stehe für den Kleene-Stern, + für die positive transitive Hülle,  \cdot für die Konkatenation zweier Zeichenreihen-Mengen und  \cup für deren gewöhnliche Vereinigung (in dieser Priorität - Klammerung wird entsprechend vernachlässigt). Dann gilt folgende Äquivalenz:

 \left( \forall Y \subseteq \Sigma^+ \right) \left( \forall Z \subseteq \Sigma^* \right) \left( \left( X = Y \cdot X \cup Z \right) \leftrightarrow \left( X = Y^* \cdot Z \right) \right)

bzw. folgende Gleichung:

 \left( \forall Y \subseteq \Sigma^+ \right) \left( \forall Z \subseteq \Sigma^* \right) \left( \left\{ X \subseteq \Sigma^* \mid X = Y \cdot X \cup Z \right\} = \left\{ Y^* \cdot Z \right\} \right)

In Worten: Für eine beliebige Zeichenreihen-Menge Z und eine Zeichenreihen-Menge Y, welche das leere Wort ε nicht enthält, hat die Gleichung  X = Y \cdot X \cup Z nur die eine Lösung  X = Y^* \cdot Z .

Beweis

Auf die Quantisierung sei in beiden Beweisteilen der besseren Lesbarkeit halber weg verzichtet, was bei Allquantifizierung nicht weiter problematisch ist, solange keine Spezifikationen für die betreffenden Variablen vorgenommen werden. Entsprechende Stellen werden speziell behandelt.

Hinrichtung

Es sei S eine Lösung für X in der Gleichung  X = Y \cdot X \cup Z .

Obermenge

Zunächst wird die Definition des Kleene-Sternes angewendet und die Distributivität der Konkatenation über Vereinigungen genutzt:

 S \supseteq \left( Y^* \cdot Z = \left( \bigcup_{n \ge 0} Y^n \right) \cdot Z = \bigcup_{n \ge 0} Y^n \cdot Z \right)

Nun lässt sich durch vollständige Induktion über n zeigen, dass  S \supseteq Y^n \cdot Z für alle  n \ge 0 gilt:

  • Induktions-Hypothese

 S \supseteq Y^n \cdot Z

  • Induktions-Anfang

 \left( S \supseteq Z \right) \rightarrow \left( S \supseteq \left\{ \varepsilon \right\} \cdot Z \right) \rightarrow \left( S \supseteq Y^0 \cdot Z \right)

  • Induktions-Schritt

 \left( S \supseteq Y \cdot S \cup Z \right) \rightarrow \left( S \supseteq Y \cdot S \right) \rightarrow \left( S \supseteq Y \cdot Y^n \cdot Z \right) \rightarrow \left( S \supseteq Y^{n+1} \cdot Z \right)

Da für verschiedene n alle Yn paarweise disjunkt sind, folgt aus  \left( \forall n \ge 0 \right) \left( S \supseteq Y^n \right) auch die ursprüngliche Obermengen-Beziehung  S \supseteq Y^* \cdot Z .

Untermenge

Hier wird der Beweis indirekt geführt: Man nimmt an,  S \subseteq Y^* \cdot Z gilt nicht, womit es mindestens ein Wort w mit  \left( w \in S \right) \wedge \left( w \notin Y^*Z \right) geben muss. Weil  S = Y \cdot S \cup B ist, muss w auch Element von  Y \cdot S \cup Z sein oder anders formuliert  \left( w \in Y \cdot S \right) \vee \left( w \in Z \right) . Im ersten Fall setzt sich w aus zwei Teilwörtern  y \in Y und  s \in S zusammen, also w = ys. Da y nicht das leere Wort sein kann (die Quantifizierung fordert  Y \subseteq \Sigma^+ ), folgt  \left| s \right| < \left| w \right| . Betrachtet man das kleinste der als existierenden angenommenen w, dann müsste außerdem  s \in Y^*Z gelten, was aber im Widerspruch zur Annahme  w \notin Y^*Z steht. Im anderen Fall, also  w \in Z , ergibt sich ebenfalls der Widerspruch  w \in Y^*Z . Da beide Fälle in Widersprüchen enden, muss die Annahme falsch gewesen sein, dass  S \subseteq Y^n \cdot Z nicht gilt.

Rückrichtung

Diese Beweisrichtung ist trivial, da es reicht zu zeigen, dass Y * Z die Gleichung  X = Y \cdot X \cup Z überhaupt löst:

 \left( X = Y^* \cdot Z \right) \rightarrow \left( X = \left( Y^+ \cup \left\{ \varepsilon \right\} \right) \cdot Z \right) \rightarrow \left( X = \left( Y \cdot Y^* \cup \left\{ \varepsilon \right\} \right) \cdot Z \right) \rightarrow \left( X = Y \cdot Y^* \cdot Z \cup \left\{ \varepsilon \right\} \cdot Z \right) \rightarrow \left( X = Y \cdot X \cup Z \right)

Anwendung

Die zentrale Bedeutung des Arden-Lemmas ist seine Anwendung in der Automatentheorie. Es erleichtert das Ermitteln der mengentechnischen Beschreibung, der von einem Nichtdeterministischen endlichen Automaten (NEA) akzeptierten Sprache:

Betrachtet wird ein NEA  \mathcal{A} = \left( Q, \Sigma, \Delta, i, F \right) , dessen Zustände mit den natürlichen Zahlen von 1 bis n bezeichnet sein sollen (also  Q = \left\{ 1, 2, \ldots, n \right\} ). Zusätzlich werden folgende Definitionen herangezogen:

 A_{q, r} = \left\{ \sigma \in \Sigma \mid \left( q, \sigma, r \right) \in \Delta \right\}

 B_q = \begin{cases} \left\{ \varepsilon \right\} & q \in F \\ \left\{ \right\} & q \notin F \end{cases}

Mit Hilfe dieser Mengen lässt sich die Teilsprache jedes Zustands  q \in Q angeben:

 L_q = \left( \bigcup_{r \in Q} A_{q, r} \cdot L_r \right) \cup B_q

Durch die Definition von Lq erhält man ein Gleichungs-System mit n Gleichungen:

 \begin{array}{c} L_1 = A_{1, 1} \cdot L_1 \cup A_{1, 2} \cdot L_2 \cup \ldots \cup A_{1, n} \cdot L_n \cup B_1 \\ L_2 = A_{2, 1} \cdot L_1 \cup A_{2, 2} \cdot L_2 \cup \ldots \cup A_{2, n} \cdot L_n \cup B_2 \\ \vdots \\ L_n = A_{n, 1} \cdot L_1 \cup A_{n, 2} \cdot L_2 \cup \ldots \cup A_{n, n} \cdot L_n \cup B_n \end{array}

Nun bringt man eine Teilsprache auf eine geeignete Form, welche eine Anwendung des Lemmas ermöglicht:

 L_q = A_{q, q} \cdot L_q \cup \left( \left( \bigcup_{r \in Q \setminus \left\{ q \right\} } A_{q, r} \cdot L_r \right) \cup B_q \right)

Laut Arden's Lemma ist diese Aussage äquivalent zu folgender:

 L_q = A_{q, q}^* \cdot \left( \left( \bigcup_{r \in Q \setminus \left\{ q \right\} } A_{q, r} \cdot L_r \right) \cup B_q \right)

Diese Lösung ist eindeutig. Setzt man nun Lq in alle anderen Gleichungen ein, so erhält man ein Gleichungs-System mit einer Variable weniger und kann so auf diese Weise immer weiter bis zum trivialen Fall vereinfachen, bei dem nur noch eine Gleichung übrig ist, welche man unabhängig von allen anderen Teilsprachen lösen kann. Durch Rückwärts-Einsetzen erhält man dann auch die übrigen Teilsprachen um schlussendlich die eindeutige Lösung des gesamten Gleichungs-Systems zu ermitteln und mit Li die vom Automaten  \mathcal{A} akzeptierte Sprache  L(\mathcal{A}) zu identifizieren.

Algebraische Betrachtung

Aus Sicht der abstrakten Algebra stellt  \left( \mathcal{P} \left( \Sigma^* \right), \cup, \cdot \right) die Struktur eines Dioids dar, was heißt, dass sowohl  \left( \mathcal{P} \left( \Sigma^* \right), \cup \right) als auch  \left( \mathcal{P} \left( \Sigma^* \right), \cdot \right) einen Monoiden bilden und  \cdot distributiv über  \cup ist. Das neutrale Element bezüglich der Vereinigung ist die leere Menge und das neutrale Element bezüglich der Konkatenation ist  \left\{ \varepsilon \right\} . Aufgrund der fehlenden Invertierbarkeit ist es im Allgemeinen nicht möglich Gleichungen über dieser Struktur zu lösen. Das Lemma von Arden ermöglicht es aber zumindest die Lösungen einiger spezieller Gleichungen zu ermitteln und das sogar eindeutig.

Beispiele

Einfache Beispiele

 \left( X = \left\{ a \right\} \cdot X \cup \left\{ b \right\} \right) \quad \leftrightarrow \quad \left( X = \left\{ a \right\}^* \cdot \left\{ b \right\} = \left\{ a^nb \mid n \ge 0 \right\} = \left\{ b, ab, aab, aaab \ldots \right\} \right)

 \left( X = \left\{ 0, 1 \right\} \cdot X \cup \left\{ u, v \right\} \right) \quad \leftrightarrow \quad \left( X = \left\{ 0, 1 \right\}^* \cdot \left\{ u, v \right\} = \left\{ u, v, 0u, 0v, 1u, 1v, 00u, 00v, 01u, 01v, 10u, 10v, \ldots \right\} \right)

Komplex-Beispiel

 \mathcal{A} = \left( \left\{ S_0, S_1, S_2, S_3, S_4 \right\}, \left\{ 0, 1 \right\}, \Delta, S_0, \left\{ S_1, S_3 \right\} \right)

 \Delta = \left\{ (S_0, \varepsilon, S_1), (S_0, \varepsilon, S_3), (S_1, 0, S_2), (S_1, 1, S_1), (S_2, 0, S_1), (S_2, 1, S_2), (S_3, 0, S_3), (S_3, 1, S_4), (S_4, 0, S_4), (S_4, 1, S_3) \right\}

NFAexample.svg


Man erhält damit das folgenden Gleichungs-System:

 \begin{array}{lclcl} L_{S_0} & = & \{\,\} \cdot L_{S_0} \cup \left\{ \varepsilon \right\} \cdot L_{S_1} \cup \{\,\} \cdot L_{S_2} \cup \left\{ \varepsilon \right\} \cdot L_{S_3} \cup \{\,\} \cdot L_{S_4} & = & L_{S_1} \cup L_{S_3} \\ L_{S_1} & = & \{\,\} \cdot L_{S_0} \cup \left\{ 1 \right\} \cdot L_{S_1} \cup \left\{ 0 \right\} \cdot L_{S_2} \cup \{\,\} \cdot L_{S_3} \cup \{\,\} \cdot L_{S_4} \cup \left\{ \varepsilon \right\} & = & \left\{ 1 \right\} \cdot L_{S_1} \cup \left\{ 0 \right\} \cdot L_{S_2} \cup \left\{ \varepsilon \right\} \\ L_{S_2} & = & \{\,\} \cdot L_{S_0} \cup \left\{ 0 \right\} \cdot L_{S_1} \cup \left\{ 1 \right\} \cdot L_{S_2} \cup \{\,\} \cdot L_{S_3} \cup \{\,\} \cdot L_{S_4} & = & \left\{ 0 \right\} \cdot L_{S_1} \cup \left\{ 1 \right\} \cdot L_{S_2} \\ L_{S_3} & = & \{\,\} \cdot L_{S_0} \cup \{\,\} \cdot L_{S_1} \cup \{\,\} \cdot L_{S_2} \cup \left\{ 0 \right\} \cdot L_{S_3} \cup \left\{ 1 \right\} \cdot L_{S_4} \cup \left\{ \varepsilon \right\} & = & \left\{ 0 \right\} \cdot L_{S_3} \cup \left\{ 1 \right\} \cdot L_{S_4} \cup \left\{ \varepsilon \right\} \\ L_{S_4} & = & \{\,\} \cdot L_{S_0} \cup \{\,\} \cdot L_{S_1} \cup \{\,\} \cdot L_{S_2} \cup \left\{ 1 \right\} \cdot L_{S_3} \cup \left\{ 0 \right\} \cdot L_{S_4} & = & \left\{ 1 \right\} \cdot L_{S_3} \cup \left\{ 0 \right\} \cdot L_{S_4} \end{array}


Durch die Anwendung des Lemmas erhält man schrittweise die Lösung:

 L_{S_2} = \left\{ 0 \right\} \cdot L_{S_1} \cup \left\{ 1 \right\} \cdot L_{S_2}

 \rightarrow \quad L_{S_2} = \left\{ 1 \right\} ^* \cdot \left\{ 0 \right\} \cdot L_{S_1}


 L_{S_1} = \left\{ 1 \right\} \cdot L_{S_1} \cup \left\{ 0 \right\} \cdot L_{S_2} \cup \left\{ \varepsilon \right\} = \left\{ 1 \right\} \cdot L_{S_1} \cup \left\{ 0 \right\} \cdot \left\{ 1 \right\} ^* \cdot \left\{ 0 \right\} \cdot L_{S_1} \cup \left\{ \varepsilon \right\} = \left( \left\{ 1 \right\} \cup \left\{ 0 \right\} \cdot \left\{ 1 \right\} ^* \cdot \left\{ 0 \right\} \right) \cdot L_{S_1} \cup \left\{ \varepsilon \right\}

 \rightarrow \quad L_{S_1} = \left( \left\{ 1 \right\} \cup \left\{ 0 \right\} \cdot \left\{ 1 \right\} ^* \cdot \left\{ 0 \right\} \right) ^*


 L_{S_4} = \left\{ 1 \right\} \cdot L_{S_3} \cup \left\{ 0 \right\} \cdot L_{S_4}

 \rightarrow \quad L_{S_4} = \left\{ 0 \right\}^* \cdot \left\{ 1 \right\} \cdot L_{S_3}


 L_{S_3} = \left\{ 0 \right\} \cdot L_{S_3} \cup \left\{ 1 \right\} \cdot L_{S_4} \cup \left\{ \varepsilon \right\} = \left\{ 0 \right\} \cdot L_{S_3} \cup \left\{ 1 \right\} \cdot \left\{ 0 \right\}^* \cdot \left\{ 1 \right\} \cdot L_{S_3} \cup \left\{ \varepsilon \right\} = \left( \left\{ 0 \right\} \cup \left\{ 1 \right\} \cdot \left\{ 0 \right\}^* \cdot \left\{ 1 \right\} \right) \cdot L_{S_3} \cup \left\{ \varepsilon \right\}

 \rightarrow \quad L_{S_3} = \left( \left\{ 0 \right\} \cup \left\{ 1 \right\} \cdot \left\{ 0 \right\}^* \cdot \left\{ 1 \right\} \right) ^*


 L_{S_0} = L_{S_1} \cup L_{S_3} = \left( \left\{ 1 \right\} \cup \left\{ 0 \right\} \cdot \left\{ 1 \right\} ^* \cdot \left\{ 0 \right\} \right) ^* \cup \left( \left\{ 0 \right\} \cup \left\{ 1 \right\} \cdot \left\{ 0 \right\}^* \cdot \left\{ 1 \right\} \right) ^*


Da S0 der Startzustand von  \mathcal{A} ist, gilt  L(\mathcal{A}) = L_{S_0} , was der dem regulären Ausdruck (1 + 01 * 0) * + (0 + 10 * 1) * zugeordneten Sprache entspricht.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Arden — steht für: Arden (Familienname), der Familienname Arden Arden International, ein Formel GP2 Team Arden Syntax, eine formale Sprache für medizinisches Wissen Arden Automobilbau, einen Automobilveredler für Jaguar und Range Rover Modelle Arden… …   Deutsch Wikipedia

  • Planet Uranus — Uranus   Uranus (Aufnahme durch Voyager 2, 1986) …   Deutsch Wikipedia

  • Winde auf dem Planeten Uranus — Uranus   Uranus (Aufnahme durch Voyager 2, 1986) …   Deutsch Wikipedia

  • — Uranus   Uranus (Aufnahme durch Voyager 2, 1986) …   Deutsch Wikipedia

  • Entwicklung der Leistungsmotivation — Die Leistungsmotivation ist nach Drever und Fröhlich eine allgemeine und relativ überdauernde Tendenz, als wesentlich bewertete Aufgaben mit Energie und Ausdauer bis zum erfolgreichen Abschluss zu bearbeiten (Drever, Fröhlich, S. 170). Das… …   Deutsch Wikipedia

  • Erfolgsmotivation — Die Leistungsmotivation ist nach Drever und Fröhlich eine allgemeine und relativ überdauernde Tendenz, als wesentlich bewertete Aufgaben mit Energie und Ausdauer bis zum erfolgreichen Abschluss zu bearbeiten (Drever, Fröhlich, S. 170). Das… …   Deutsch Wikipedia

  • Risiko-Wahl-Modell — Die Leistungsmotivation ist nach Drever und Fröhlich eine allgemeine und relativ überdauernde Tendenz, als wesentlich bewertete Aufgaben mit Energie und Ausdauer bis zum erfolgreichen Abschluss zu bearbeiten (Drever, Fröhlich, S. 170). Das… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”