To receive notifications about scheduled maintenance, please subscribe to the mailing-list gitlab-operations@sympa.ethz.ch. You can subscribe to the mailing-list at https://sympa.ethz.ch

automaten_sprachen.tex 12.6 KB
Newer Older
Theo von Arx's avatar
Theo von Arx committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
%! TEX root = DES.tex

\section{Automaten \& Sprachen}
\subsection{Alphabete und Strings}
\textbf{Alphabet} $\Sigma$: Eine Menge von Symbolen (Zeichen, Buchstaben) \\

\textbf{String} von $\Sigma$: Eine Sequenz von Symbolen. $|.|$ bezeichnet die Länge eines Strings. \\
Der leere String $\varepsilon$ hat die Länge $|\varepsilon| = 0$.


\subsection{Deterministic Finite Automaton (DFA)}
Ein finiter Automat (FA) ist ein 5-tuple ($Q, \Sigma, \delta, q_0, F$) mit
\begin{itemize}
	\item $Q$ ist eine endliche Menge genannt Zustände
	\item $\Sigma$ ist eine endliche Menge genannt Alphabet
	\item $\delta: Q \times E \to Q$ ist die Transfer Funktion
	\item $q_0 \in Q$ ist der Start Zustand
	\item $F \subseteq Q$ ist die Menge der akzeptierenden Zustände (final states)
\end{itemize}

Der DFA liest den Inputstring von links nach rechts und wechselt bei jedem Symbol den Zustand. Falls der DFA am Ende des Inputstrings in einem akzeptierenden Zustand ist, so wird der String akzeptiert.

\begin{fdef}
	Ein String $u$ wird akzeptiert von einem Automaten M genau dann, wenn der Pfad, der in $q_0$ startet, mit $u$ angeschrieben ist und $u$ in einem akzeptierenden Zustand endet.
\end{fdef}

\subsection{Sprachen}
\begin{fdef}
	Die Sprache, die von einem DFA $M$ akzeptiert wird, ist die Menge aller Strings, die vom DFA $M$ akzeptiert werden. Die Sprache wird durch $L(M)$ angegeben. Wir sagen auch, dass $M$ $L(M)$ erkennt oder dass $M$ $L(M)$ akzeptiert.
\end{fdef}
\\

Eine Sprache wird eine \textbf{reguläre Sprache} gennant, falls ein DFA $M$ existiert, der die Sprache $L$ erkennt.

\begin{ftext}
	Theorem: Alle endlichen Sprachen ($|L(M)|$ ist endlich) sind regulär.
\end{ftext} \\

Die leere Sprache $\emptyset$ akzeptiert keinen String (auch nicht $\varepsilon$).

\subsection{Regular operations}
Wenn reguläre Operationen auf reguläre Sprachen angewandt werden, so entstehen wieder reguläre Sprachen. Reguläre Sprachen sind geschlossen unter den Operationen Union, Concatenation, Kleene-$^\star$ und Kleene-$^+$.

\subsubsection{Union}
$A \cup B$ bedeutet, dass der String akzeptiert wird, falls $A$ oder $B$ den String akzeptieren.

\subsubsection{Concatenation}
$A \cdot B$ bedeutet, dass der erste Teil des Strings von $A$ akzeptiert werden muss und der zweite Teil von $B$. Die Trennung ist dabei beliebig. \\

Es gilt: $L \cdot \{\varepsilon \} = L$ \\
$L \cdot \emptyset = \emptyset$

\subsubsection{Kleene-$^\star$}
$A^{\star}$ heisst, dass $A$ beliebig oft (auch 0 mal) wiederholt werden kann. Falls $A$ 0 mal wiederholt wird, so entspricht dies $\varepsilon$.

\subsubsection{Kleene-$^+$}
Sehr ähnlich zu Kleene-$^\star$, jedoch muss $A$ mindestens einmal vorkommen. Man kann dies darstellen als $A^+ = A \cdot A^\star$


\subsection{Kartesisches Produkt}
Das kartesische Produkt $A \times B$ von zwei Mengen $A$ und $B$ ist die Menge aller geordneten Paare $(a, b)$ mit $a \in A$ und $b \in B$. (alle Kombinationen von $A$ und $b$)

Gegeben seien zwei zwei DFAs $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ und $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$. Diese können nun unter verschiedenen Operationen zusammengefügt werden:

\begin{itemize}
	\item Vereinigung ($A \cup B$): Entweder $M_1$ oder $M_2$ müssen akzeptierend sein: \\ $M_\cup = (Q_1 \times Q_2, \Sigma, \delta_1 \times \delta_2, (q_1, q_2), F_\cup)$ mit $F_\cup = Q_1 \times F_2 \cup F_1 \times Q_2$
	\item Schnitt ($A \cap B$): Beide müssen akzeptierend sein: \\
		$M_\cap = (Q_1 \times Q_2, \Sigma, \delta_1 \times \delta_2, (q_{0,1}, q_{0,2}), F_\cap)$ mit $F_\cap = F_1 \times F_2$
	\item Differenz ($A - B = \{ x \in A \, | \, x \notin B \}$): Akzeptiere, wenn $A$ akzeptiert aber $B$ nicht: \\
		$M_{-} = (Q_1 \times Q_2, \Sigma, \delta_1 \times \delta_2, (q_{0,1}, q_{0,2}), F_{-})$ mit $F_{-} = F_1 \times Q_2 - Q_1 \times F_2$
	\item Symmetrische Differenz ($A \oplus B = A \cup B - A \cap B$): Akzeptiere, wenn genau ein Automat akzeptiert: \\
		$M_{\oplus} = (Q_1 \times Q_2, \Sigma, \delta_1 \times \delta_2, (q_{0,1}, q_{0,2}), F_\oplus)$ mit $F_\oplus = F_\cup - F_\cap$
	\item Komplement ($\overline{L}$): Vertausche die akzeptierenden mit den nicht akzeptierenden Zuständen.
\end{itemize}


\subsection{Nondeterministic Finite Automaton (NFA)}
Ein nicht deterministischer enlicher Automat (NFA) ist gegeben durch $M = (Q, \Sigma, \delta, q_0, F)$, genau gleich wie ein FA, jedoch hat $\delta$ eine andere Definition
\[
	\delta: Q \times \Sigma_\varepsilon \to P(Q)
\]

$P(Q)$ bezeichnet die Potenzmenge (die Menge aller Teilmengen von $Q$). \\
$\Sigma_\varepsilon = \Sigma \cup \{ \varepsilon \}$

\begin{fdef}
	Ein String $u$ wird vom NFA $M$ akzeptiert genau dann, wenn ein Pfad existiert, der bei $q_0$ startet, mit dem Label $u$ angeschrieben ist und in einem akzeptierenden Zustand endet. Die von $M$ akzeptierte Sprache wird mit $L(M)$ bezeichnet.
\end{fdef}
\\

Einem Label $\varepsilon$ zu folgen ist gratis, es wird nicht vom Input gelesen. Im Label des Pfades sollten alle $\varepsilon$ entfernt werden.

\subsubsection{Reguläre Operationen für NFAs}
Im folgenden Bild bezeichnet der Block einen NFA, wobei die hellgraue Fläche die nicht akzeptierenden Zustände darstellt, die (dunkelgraue/)grüne Fläche die akzeptierenden. Der rote Punkt steht für den Startzustand.

\begin{figure}[H]
	\centering
	\includegraphics[scale=0.35]{fig/nfa-block}
\end{figure}

\begin{itemize}
	\item Union
		\begin{figure}[H]
			\centering
			\includegraphics[scale=0.35]{fig/nfa-union}
		\end{figure}

	\item Concatenation
		\begin{figure}[H]
			\centering
			\includegraphics[scale=0.35]{fig/nfa-concatenation}
		\end{figure}

	\item Kleene-$^+$
		\begin{figure}[H]
			\centering
			\includegraphics[scale=0.35]{fig/nfa-kleeneplus}
		\end{figure}

	\item Kleene-$^\star$
		\begin{figure}[H]
			\centering
			\includegraphics[scale=0.35]{fig/nfa-kleenestar}
		\end{figure}
\end{itemize}

\begin{ftext}
	Theorem: Wenn $L_1$ und $L_2$ von NFAs akzeptiert werden, so werden auch $L_1 \cup L_2, L_1 \cdot L_2, L_1^+$ und $L_1^\star$ von einem NFA akzeptiert. Diese NFAs können in linearer Zeit konstruiert werden.
\end{ftext}


\subsection{Reguläre Ausdrücke (REX)}
\begin{figure}[H]
	\centering
	\includegraphics[width=\columnwidth]{fig/rex-table}
\end{figure}

Es gilt die Operatorrangfolge: $^\star, \cdot, \cup$
\\

Es gilt speziell: \\
$L(\varepsilon) = \{ \varepsilon \}$ \\
$L(\emptyset) = \{ \} = \emptyset$ und $1^\star \emptyset = \emptyset$


\subsection{REX $\to$ NFA}
\begin{ftext}
	Theorem: Für jeden regulären Ausdruck $r$ gibt es einen NFA $N$, der $r$ simuliert. Das heisst, die Sprache von $N$ ist genau die Sprache, die von $r$ generiert wird, so dass $L(N) = L(r)$. Der NFA lässt sich ausserem in linearer Zeit konstruieren.
\end{ftext}
\\

Aus den folgenden 3 Basisoperationen und den Operationen Union, Concatenation, Kleene-$^\star$ und Kleene-$^+$ lassen sich alle regulären Sprachen zusammenbauen.

\begin{figure}[H]
	\centering
	\begin{subfigure}[b]{0.3\textwidth}
		\centering
		\includegraphics[scale=0.4]{fig/rex-nfa-a}
		\caption*{$a \in \Sigma$}
	\end{subfigure}
	\begin{subfigure}[b]{0.3\textwidth}
		\centering
		\includegraphics[scale=0.4]{fig/rex-nfa-epsilon}
		\caption*{$\varepsilon$}
	\end{subfigure}
	\begin{subfigure}[b]{0.3\textwidth}
		\centering
		\includegraphics[scale=0.4]{fig/rex-nfa-empty}
		\caption*{$\emptyset$}
	\end{subfigure}
\end{figure}

Es folgt, dass alle Sprachen, die von einem NFA akzeptiert werden, regulär sind.


\subsection{NFA $\to$ FA}
\begin{itemize}
	\item Anstelle der $n$ Zustände des NFA betrachten wir die Potenzmenge der Zustände im FA. \\
		$\Rightarrow$ FA hat $2^n$ Zustände.
	\item Zuerst finden wir heraus, welche Zustandsmenge von welchen Zustandsmengen erreicht werden. (mit den Regeln des NFA)
	\item Dann müssen alle Epsilon-Kanten eingefügt werden. Wir biegen Pfeile von $\{a, b, c \}$ um nach $\{ a, b, c, d, e, f \}$ genau dann, wenn es einen Nur-Epsilon-Pfad gibt, der von einem der Zustände $a, b, c$ zu den Zuständen $d, e, f$ zeigt. \\
		Das gleiche machen wir auch mit dem Startzustand. Falls z.B. im NFA der Startzustand $1$ ist und wir eine Epsilon-Kante von 1 nach 2 haben, so ist der Startzustand im FA $\{1, 2\}$.
	\item Die akzeptierenden Zustände im FA sind alle diejenigen Zustände, die einen akzeptierenden Zustand enthalten.
\end{itemize}

Manchmal gibt es offensichtliche Vereinfachungen für den resultierenden FA, da dieses Rezept meist einen komplexeren FA generiert, als notwendig wäre. Ansonsten kann der Automat auch später noch vereinfacht werden.
\\

\begin{bsp}
	\hspace*{0pt}\\
	\includegraphics[width=0.9\columnwidth]{fig/nfa-fa-bsp}
\end{bsp}

\begin{ftext}
	Theorem: Falls $L$ eine von einem NFA akzeptierte Sprache ist, so existiert ein konstruierbarer DFA, der die Sprache $L$ akzeptiert.
\end{ftext}



\subsection{NFA $\to$ REX}
Um aus einem NFA eine REX zu bekommen, machen wir einen Umweg über GNFA (generalized nondeterministic finite automaton). \\
Ein GNFA ist ein Graph, dessen Kanten mit regulären Ausdrücken beschriftet sind:
\begin{itemize}
	\item Der Startzustand muss eindeutig sein mit einem In-Grad von 0, aber Kanten zu allen anderen Zuständen.
	\item Der Endzustand muss eindeutig sein mit einem Aus-Grad von 0, aber Kanten von allen anderen Zuständen. (Anfangszustand $\neq$ Endzustand)
	\item Alle anderen Zustände dürfen eingehende und ausgehende Kanten von allen Zuständen haben, sogar zu sich selbst.
\end{itemize}

Nun muss der GNFA vereinfacht werden, bis nur noch zwei Zustände (Anfangs- und Endzustand) übrig bleiben. Die REX kann dann direkt von dem einzig verbliebenen Label abgelesen werden.

\subsubsection{Vorgehen}
\begin{enumerate}
	\item Konstruiere GNFA aus einem FA
		\begin{enumerate}
			\item Falls mehr als ein Pfeil von einem Zustand zu einem anderen Zustand existieren, vereinige diese mit $\cup$
			\item Erstelle einen eindeutigen Startzustand mit In-Grad 0.
			\item Erstelle einen eindeutigen Endzustand mit Aus-Grad 0.
		\end{enumerate}
	\item Wiederhole: So lange der GNFA mehr als 2 Zustände hat:
		Entferne beliebige innere Zustände und passe die Labels entsprechend an.
	\item Die REX ist das verbliebene Label
\end{enumerate}

\paragraph*{Innere Zustände entfernen} \hspace*{0pt}\\
Wir entfernen den Zustand $v$.
\begin{figure}[H]
	\centering
	\includegraphics[scale=0.4]{fig/gnfa-1}
\end{figure}

Damit keine Möglichkeiten verloren gehen, müssen wir die REX von u nach w anpassen
\begin{figure}[H]
	\centering
	\includegraphics[scale=0.4]{fig/gnfa-2}
\end{figure}

\subsection{Vereinfachung}
\begin{fdef}
	Ein Automat ist nicht weiter reduzierbar falls
	\begin{itemize}
		\item er keinen nutzlosen Zustand enthält und
		\item keine zwei Zustände äquivalent sind
	\end{itemize}
\end{fdef}


\subsection{Pumping Lemma}
\begin{ftext}
	Pigeonhole Principle: Wenn $m$ Tauben auf $n < m$ Taubenschläge verteilt werden müssen, so muss in mindestens einem Taubenschlag mehr als eine Taube sein.
\end{ftext}
\\

Wir betrachten eine Sprache $L$ mit Strings $w \in L$ und einen FA mit $n < |w|$ Zuständen. Nach dem Pigeonhole principle muss der FA mindestens einen Zustand mehrfach besuchen, um $L$ zu akzeptieren. Das bedeutet, dass reguläre Sprachen mit unbegrenzt langen Strings nur dann von einem FA akzeptiert werden können, falls diese Strings sich irgendwo wiederholen.

\begin{ftext}
	Theorem: Gegeben eine reguläre Sprache $L$, dann existiert eine Zahl $p$ (die Pumping Zahl), so dass alle Strings in $L$ mit Länge $\geq p$ pumpbar sind innerhalb ihrer ersten $p$ Buchstaben.
\end{ftext}
\\

In anderen Worten: Für alle $u \in L$ mit $|u| \geq p$ muss gelten:
\begin{itemize}
	\item $u = x \, y \, z$ \hspace{100pt} x ist ein Prefix, z ist ein Suffix
	\item $|y| \geq 1$		\hspace{110pt} mittlerer Teil $y$ ist nicht leer
	\item $|x y | \leq p$	\hspace{105pt} Pumpen erfolgt in den ersten $p$ Buchstaben
	\item $x y^i z \in L$ für alle $i \geq 0$	\hspace{40pt}	wir können y pumpen. $i$ darf 0 sein.
\end{itemize}

Falls kein solches $p$ existiert, so ist die Sprache nicht regulär.
\\

Um zu beweisen, dass eine Sprache nicht regulär ist, muss man zeigen, dass für alle Wahlmöglichkeiten $y$ die es gibt, keine die genannten Eigenschaften erfüllt.


TODO: Hier noch mehr zum Vorgehen einfügen. Siehe dazu Sipser Buch

\subsubsection{Beweis von nicht Regularität}
Die folgende Argumentation basiert auf der Geschlossenheit der regulären Sprachen und Operatoren, sie funktioniert nur in diese Richtung. \\
Es gilt: Für einen Operator $\diamond \in \{ \cup, \cap, \cdot \}$ gilt
\[
	\text{Falls $L_1$ und $L_2$ regulär sind, so ist auch $L_1 \diamond L_2$ regulär}
\]
Falls entweder $L_1$ oder $L_2$ oder beide nicht regulär sind, so können wir nicht auf die nicht Regularität von $L$ schliessen oder umgekehrt. \\
Ebenso, dass $L$ regulär ist, bedeutet nicht, dass $L_1$ und $L_2$ auch regulär sind.