Nichtdeterministische Endliche Automaten - Versionsgeschichte

Jana am 26. August 2018 um 16:33 Uhr

2018-08-26T16:33:03Z

2018-08-01T17:05:36Z

‎Abschlusseigenschaften

2018-08-01T15:43:58Z

‎Kleene-Hülle

2018-08-01T15:36:49Z

‎Schnitt

2018-08-01T15:36:02Z

‎Vereinigung

2018-08-01T15:33:42Z

‎Konkatenation

2018-08-01T15:33:21Z

‎Vereinigung

2018-08-01T15:28:05Z

‎Konkatenation

2018-08-01T15:03:14Z

‎Negation/Komplement

2018-08-01T14:55:07Z

‎Singletons

@@ Zeile 185: / Zeile 185: @@
 Die Kleene-Hülle $A*$ einer Sprache $A$ ist definiert als $\{\varepsilon\}\cup A\cup AA\cup AAA\cup\ldots$, also alle endlichen Wiederholungen von Wörtern aus $A$. Akzeptiert der Automat $M$ mit Anfangszustand $q_0$ und mit Endzuständen $q_1,\ldots,q_n$ die Sprache $A$, so wird $A*$ akzeptiert von
-                +--ε---------+
+                +--ε----------+
-                |            |
+                |             |
-                |       +-->((q1))
+                |        +-->((q1))
-                V       |
+                V        |
-          ---->(q0)-->[M]   ...
+          ---->((q0))-->[M]   ...
-              A |A     |
+                 A      |
-              | ||     +->((qn))
+                 |      +->((qn))
-              +ε+|          |
+                 |           |
-                  +---ε------+
+                  +---ε-------+

← Nächstältere Version		Version vom 1. August 2018, 17:05 Uhr
Zeile 128:		Zeile 128:

	== Abschlusseigenschaften ==		== Abschlusseigenschaften ==
		+
		+	Wir zeigen hier Abschlusseigenschaften für nichtdeterministische endliche Automaten mit $\varepsilon$-Kanten. Analog zu den obigen Algorithmen kann aus den resultierenden Automaten aber jeweils wieder ein deterministischer endlicher Automat hergestellt werden. Entsprechend sind die Abschlusseigenschaften hier auch Abschlusseigenschaften für deterministische endliche Automaten.

	=== Singletons ===		=== Singletons ===

← Nächstältere Version		Version vom 1. August 2018, 15:43 Uhr
Zeile 180:		Zeile 180:

	=== Kleene-Hülle ===		=== Kleene-Hülle ===
		+
		+	Die Kleene-Hülle $A$ einer Sprache $A$ ist definiert als $\{\varepsilon\}\cup A\cup AA\cup AAA\cup\ldots$, also alle endlichen Wiederholungen von Wörtern aus $A$. Akzeptiert der Automat $M$ mit Anfangszustand $q_0$ und mit Endzuständen $q_1,\ldots,q_n$ die Sprache $A$, so wird $A$ akzeptiert von
		+
		+	+--ε---------+
		+	\| \|
		+	\| +-->((q1))
		+	V \|
		+	---->(q0)-->[M] ...
		+	A \|A \|
		+	\| \|\| +->((qn))
		+	+ε+\| \|
		+	+---ε------+

← Nächstältere Version		Version vom 1. August 2018, 15:36 Uhr
Zeile 176:		Zeile 176:

	=== Schnitt ===		=== Schnitt ===
		+
		+	Es gilt $A\cap B = \overline{\overline{A}\cup\overline{B}}$.

	=== Kleene-Hülle ===		=== Kleene-Hülle ===

@@ Zeile 167: / Zeile 167: @@
 === Vereinigung ===
-Wird eine Sprache $A$ vom Automaten $M$ mit Endzuständen $q_1,\ldots,q_n$
+Wird eine Sprache $A$ vom Automaten $M$ akzeptiert, und eine Sprache $B$ vom Automaten $N$ akzeptiert, so wird $A\cup B$ akzeptiert von
 === Schnitt ===
 === Kleene-Hülle ===

@@ Zeile 149: / Zeile 149: @@
           +-------->((qn))
-akzeptiert, und eine Sprache $B$ von einem Automaten $N$ mit den Endzuständen $r_1,\ldots, r_n$
+akzeptiert, und eine Sprache $B$ von einem Automaten $N$ mit den Endzuständen $r_1,\ldots, r_k$
           +-------->((r1))
@@ Zeile 155: / Zeile 155: @@
      --->[N]         ...
+          |
-          +-------->((rn))
+          +-------->((rk))
 so wird die Konkatenation der Sprachen, also die Sprache $AB := \{ab\mid a\in A, b\in B\}$, akzeptiert vom Automaten, bei dem von jedem Endzustand in $M$ eine $\varepsilon$-Kante zum Anfangszustand $N$ gezogen wird, also
@@ Zeile 163: / Zeile 163: @@
      --->[M]        ...      [N]  ...
           |                  A |
-          +------->(qn)---ε--+ +------>((rn))
+          +------->(qn)---ε--+ +------>((rk))
 === Vereinigung ===

← Nächstältere Version		Version vom 1. August 2018, 15:28 Uhr
Zeile 140:		Zeile 140:

	=== Konkatenation ===		=== Konkatenation ===
		+
		+	Wird eine Sprache $A$ von einem Automaten $M$ mit Endzuständen $q_1,\ldots, q_n$
		+
		+	+------->((q1))
		+	\|
		+	--->[M] ...
		+	\|
		+	+-------->((qn))
		+
		+	akzeptiert, und eine Sprache $B$ von einem Automaten $N$ mit den Endzuständen $r_1,\ldots, r_n$
		+
		+	+-------->((r1))
		+	\|
		+	--->[N] ...
		+	\|
		+	+-------->((rn))
		+
		+	so wird die Konkatenation der Sprachen, also die Sprache $AB := \{ab\mid a\in A, b\in B\}$, akzeptiert vom Automaten, bei dem von jedem Endzustand in $M$ eine $\varepsilon$-Kante zum Anfangszustand $N$ gezogen wird, also
		+
		+	+------->(q1)---ε--+ +------>((r1))
		+	\| V \|
		+	--->[M] ... [N] ...
		+	\| A \|
		+	+------->(qn)---ε--+ +------>((rn))

	=== Vereinigung ===		=== Vereinigung ===

← Nächstältere Version		Version vom 1. August 2018, 15:03 Uhr
Zeile 136:		Zeile 136:

	=== Negation/Komplement ===		=== Negation/Komplement ===
		+
		+	Ist eine Sprache $A$ gegeben, und wird von einem Automaten $M$ akzeptiert, so ist ihre Negation oder ihr '''Komplement''' definiert durch $\overline{A} := {\cal L}^*\backslash A$. Den Automaten $M$ muss man nur dahingehend verändern, dass man die Rolle von Endzustand und Zwischenzustand vertauscht. Dann werden genau die Wörter akzeptiert, die $M$ nicht akzeptiert.

	=== Konkatenation ===		=== Konkatenation ===

← Nächstältere Version		Version vom 1. August 2018, 14:55 Uhr
Zeile 130:		Zeile 130:

	=== Singletons ===		=== Singletons ===
		+
		+	Die Sprache, die nur ein einzelnes Wort der Länge 1 enthält, zum Beispiel $\{a\}$, wird akzeptiert von
		+
		+	-->(1)--a-->((2))

	=== Negation/Komplement ===		=== Negation/Komplement ===