Reguläre Ausdrücke - Versionsgeschichte

Css am 1. August 2018 um 18:23 Uhr

2018-08-01T18:23:09Z

Css am 1. August 2018 um 18:21 Uhr

2018-08-01T18:21:04Z

Css am 1. August 2018 um 18:13 Uhr

2018-08-01T18:13:25Z

Css am 1. August 2018 um 18:07 Uhr

2018-08-01T18:07:33Z

Css: Die Seite wurde neu angelegt: „Reguläre Ausdrücke sind rekursiv definiert: * Die leere Zeichenkette $\varepsilon$ ist ein regulärer Ausdruck * Für jedes $a\in{\cal L}$ ist das singleton…“

2018-08-01T17:16:22Z

Die Seite wurde neu angelegt: „Reguläre Ausdrücke sind rekursiv definiert: * Die leere Zeichenkette $\varepsilon$ ist ein regulärer Ausdruck * Für jedes $a\in{\cal L}$ ist das singleton…“

Neue Seite

Reguläre Ausdrücke sind rekursiv definiert:

* Die leere Zeichenkette $\varepsilon$ ist ein regulärer Ausdruck
* Für jedes $a\in{\cal L}$ ist das singleton $a$ ein regulärer Ausdruck
* Sind $x,y$ reguläre Ausdrücke, so ist die Verkettung $xy$ ein regulärer Ausdruck
* Sind $x,y$ reguläre Ausdrücke, so ist die Alternative $(x|y)$ ein regulärer Ausdruck
* Ist $x$ ein regulärer Ausdruck, so ist $(x*)$, also die Kleene'sche Hülle von $x$, ein regulärer Ausdruck

Die Semantik ist definiert als

* $\varepsilon\models\emptyset$
* ${\cal L}\ni a\models\{a\}$
* $x\models A$, $y\models B$, dann $xy\models AB$
* $x\models A$, $y\models B$, dann $(x|y)\models A\cup B$
* $x\models A$, dann $(x*)\models A*$

Die Abschlusseigenschaften deterministischer endlicher Automaten zeigen, dass jeder reguläre Ausdruck durch einen deterministischen endlichen Automaten dargestellt werden kann.

← Nächstältere Version		Version vom 1. August 2018, 18:23 Uhr
Zeile 32:		Zeile 32:

	Nun werden die Kanten vereinigt		Nun werden die Kanten vereinigt
−

	(q1)------a1 (b1\|...\|bm)* a[k+1]------>(q[k+1])		(q1)------a1 (b1\|...\|bm)* a[k+1]------>(q[k+1])

@@ Zeile 23: / Zeile 23: @@
                 +----++-----+
                      ||
-         (q1)--a1---+||+---a(k+1)--->(q(k+1))
+         (q1)--a1---+||+---a[k+1]--->(q[k+1])
                     ||||
                     V|V|
@@ Zeile 32: / Zeile 32: @@
 Nun werden die Kanten vereinigt

@@ Zeile 17: / Zeile 17: @@
 Die Abschlusseigenschaften deterministischer endlicher Automaten zeigen, dass jeder reguläre Ausdruck durch einen deterministischen endlichen Automaten dargestellt werden kann.
-Umgekehrt zeigen wir, dass es zu jedem deterministischen endlichen Automaten einen äquivalenten regulären Ausdruck gibt. Die Idee ist simpel: Wir erlauben an Kanten reguläre Ausdrücke zu stehen, und entfernen sukzessiv Zustände und deren Kanten durch neue Kanten mit regulären Ausdrücken. Für einen Zustand $q_0$ gebe es kanten hinein von Zuständen $q_1,\ldots,q_k$, und kanten hinaus in Zustände $q_{k+1}, \ldots, q_l$, beschriftet mit regulären Ausdrücken $a_1,\ldots,a_l$, die am Anfang alle singletons sind
+Umgekehrt zeigen wir, dass es zu jedem deterministischen endlichen Automaten einen äquivalenten regulären Ausdruck gibt. Die Idee ist simpel: Wir erlauben an Kanten reguläre Ausdrücke zu stehen, und entfernen sukzessiv Zustände und deren Kanten durch neue Kanten mit regulären Ausdrücken. Für einen Zustand $q_0$ gebe es kanten hinein von Zuständen $q_1,\ldots,q_k$, und kanten hinaus in Zustände $q_{k+1}, \ldots, q_l$, beschriftet mit regulären Ausdrücken $a_1,\ldots,a_l$, die am Anfang alle singletons sind, außerdem eventuell loops von $q_0$ nach $q_0$ für die Zeichen $b_1,\ldots,b_m$
-        (q1)--a1---+
+Nun werden die Kanten vereinigt

← Nächstältere Version		Version vom 1. August 2018, 18:07 Uhr
Zeile 16:		Zeile 16:

	Die Abschlusseigenschaften deterministischer endlicher Automaten zeigen, dass jeder reguläre Ausdruck durch einen deterministischen endlichen Automaten dargestellt werden kann.		Die Abschlusseigenschaften deterministischer endlicher Automaten zeigen, dass jeder reguläre Ausdruck durch einen deterministischen endlichen Automaten dargestellt werden kann.
		+
		+	Umgekehrt zeigen wir, dass es zu jedem deterministischen endlichen Automaten einen äquivalenten regulären Ausdruck gibt. Die Idee ist simpel: Wir erlauben an Kanten reguläre Ausdrücke zu stehen, und entfernen sukzessiv Zustände und deren Kanten durch neue Kanten mit regulären Ausdrücken. Für einen Zustand $q_0$ gebe es kanten hinein von Zuständen $q_1,\ldots,q_k$, und kanten hinaus in Zustände $q_{k+1}, \ldots, q_l$, beschriftet mit regulären Ausdrücken $a_1,\ldots,a_l$, die am Anfang alle singletons sind
		+
		+
		+	(q1)--a1---+
		+	\|
		+	V
		+	... (q0)
		+	A
		+	\|
		+	(qk)--ak---+