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

inelligenteAutomaten.tex 15 KB
Newer Older
zrene's avatar
zrene committed
1
%! TEX root = ../DES.tex
Theo von Arx's avatar
Theo von Arx committed
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

\section{Intelligentere Automaten}
\subsection{Kontext-freie Grammatik (CFG)}
Definition: Eine kontext-freie Grammatik besteht aus dem 4-Tupel $(V, \Sigma, R, S)$ mit
\begin{itemize}
	\item $V$: Einer endlichen Menge von Variablen
	\item $\Sigma$: Einer endlichen Menge von Terminals (oder dem Alphabet). Terminals dürfen nicht in $V$ vorkommen.
	\item $R$: Einer endlichen Menge von Regel (oder Produktionen) der Form \\
		$v \to w$ mit $v \in V$ und $w \in (\Sigma_\varepsilon \cup V)^*$
	\item $S \in V$: Dem Start Symbol. Falls nicht explizit angegeben ist das Startsymbol dasjenige in der ersten Regel links.
\end{itemize}

Defintion: Das Ableitungssymbol ''$\Rightarrow$'' steht für eine Beziehung zwischen Strings in $(\Sigma \cup V)^*$. Wir schreiben $x \Rightarrow y$ falls $x$ und $y$ aufgeteilt werden können in $x = sAt$ und $y = sWt$ und $v \to w$ eine Regel in $R$ ist.
\\

Definition: Das Ableitungssymbol ''$\Rightarrow^*$'' steht für eine Beziehung zwischen Strings in $(\Sigma \cup V)^*$. Wir schreiben $x \Rightarrow^* y$ falls eine Sequenz von Regeln existiert die $x$ in $y$ überführt. Das bedeutet $x_0 \Rightarrow x_1, x_1 \Rightarrow x_2, \ldots, x_{n-1} \Rightarrow x_n = y$.
\\

Definition: Sei $G$ eine kontext-freie Grammatik. Die kontext-freie Sprache (CFL) die von G generiert wird ist die Menge aller Terminal-Strings, die vom Startsymbol abgeleitet werden können.\\
Man schreibt: $L(G) = \{w \in \Sigma^* \, | \, S \Rightarrow^* w \}$
\\

\subsubsection{Ableitungsbäume}
Ein einem Ableitungsbaum (oder Parsebaum) entspricht jedem Konten ein Symbol. Jeder Elternknoten ist ein Symbol, wobei nach den Regeln der CFG weitere Knoten unterhalb angefügt werden. \\
Beispiel für $v \to abcdefg$

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

Der Stamm ist immer die Startvariable. \\
Die Blätter werden aus dem String von links nach rechts abgeleitet. (Die Variable am meisten links zuerst auswerten.)

\subsubsection{Mehrdeutigkeit}
Es gibt mehrere Möglichkeiten eine Regel einer CFG auszuwerten. Die bekanntesten sind \textbf{Left-most derivation}, wo zuerst das Symbol am meisten links ersetzt wird und \textbf{Right-most derivation}, wo zuerst das Symbol am meisten rechts ersetzt wird. \\
Diese unterschiedlichen Ansätze könne zu komplett unterschiedlichen Terminalstrings führen.
\\

Definition: Einen String $x$ nennt man mehrdeutig, falls es zwei komplett verschiedene Wege gibt $x$ in G abzuleiten. Eine Grammatik nennt man mehrdeutig, falls es einen String $x$ in $L(G)$ gibt der mehrdeutig ist.


\subsection{Prüfen ob $L = L(G)$}
Sei $G$ eine CFG und $L$ eine Sprache. Um zu zeigen, dass $L(G) = L$ gilt, muss folgendes gelten
\begin{itemize}
	\item $L \subseteq L(G)$: Jeder String in $L$ kann generiert werden durch $G$.
	\item $L \supseteq L(G)$: $G$ generiert nur Strings von $L$.
\end{itemize}

TODO: Evtl hier noch ein Beispiel anfügen


\subsection{Designen von kontext-freie Grammatik}

\begin{itemize}
	\item Falls die CFG ein Union von einfacheren Grammatiken ist, so kann man $S \to S_1 | S_2$ verwenden, wobei $S_1$ bzw. $S_2$ die Startsymbole der einfacheren Grammatiken sind.
	\item Falls die CFG regulär ist, so kann man zuerst den DFA designen und dann auf die CFG zurückführen.
		\begin{itemize}
			\item Jeder Zustand wird zu einer Variable.( $q_i$ wird zu $V_i$)
			\item Erstellen der Regel $R_i \to a R_j$ falls $\delta(q_i, a) = q_j$
			\item Für akzeptierende Zustände erstellen wir die Regel $R_i \to \varepsilon$.
			\item Für den Startzustand ist $S = q_0$
		\end{itemize}
\end{itemize}

\subsection{Push-down Automaten (PDA)}
PDAs sind Automaten, die CFGs realiseren können. Die Beschreibung durch eine CFG und einen PDA sind äquivalent. Der PDA erhält im Gegensatz zu den DFA/NFA noch einen Stack auf dem folgende Basisoperationen möglich sind
\begin{itemize}
	\item \textbf{Push}: Ein neues Element zuoberst auf den Stack legen ($\varepsilon \to a$)
	\item \textbf{Pop}: Das oberste Element vom Stack entfernen ($a \to \varepsilon$)
	\item \textbf{Peek}: Das oberste Element überprüfen, ohne es zu entfernen
\end{itemize}

Um den leeren Stack zu erkennen wird oft ein spezielles Symbol als erstes auf den Stack gepusht ($\varepsilon \to \$$), das am Ende wieder entfernt wird ($\$ \to \varepsilon$).
\\


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

\subsubsection{Formale Definition eines PDA}
Ein Push-down Automat (PDA) ist ein 6-Tuple $ M = (Q, \Sigma, \Gamma, \delta, q_0, F)$:
\begin{itemize}
	\item $Q, \Sigma, q_0$ und $F$ sind definiert wie bei einem DFA
	\item $\Gamma$ ist das Stack Alphabet
	\item $\delta$ ist die Übergangsfunktion, bestimmt durch den aktuellen Zustand $p$, den nächsten Input $x$ und das oberste Symbol auf dem Stack $y$. $\delta(p, x, y)$ gibt uns alle $(q, z)$, wobei $q$ der nächste Zustand und $z$ das neue Symbol auf dem Stack ist.
		\[
			\delta: Q \times \Sigma_\varepsilon \times \Gamma_\varepsilon \to P(Q \times \Gamma_\varepsilon)
		\]
\end{itemize}

\subsection{Rechtslineare Grammatiken}
\begin{fdef}
	Eine rechtslineare Grammatik ist eine CFG, so dass alle Regeln die Form $A \to u B$ oder $A \to u$ haben, wobei $u$ ein Terminalstring und $A, B$ Variablen sind
\end{fdef}


\begin{ftext}
	Theorem: Wenn $M = (Q, \Sigma, \delta, q_0, F)$ ein NFA ist, dann gibt es eine rechtslineare Grammatik $G(M)$, die die gleiche Sprache wie $M$ generiert.
\end{ftext}
\\

Natürlich können nicht alle CFGs in eine rechtslineare Grammatik konvertiert werden, denn das würde bdeuten, das CFGs regulär sind.


\subsection{Chomsky Normal Form (CNF)}
Die CNF ist eine simpler Type einer CFG, wobei alle kontext-freien Sprachen in die Chomsky Normal Form gebracht werden können.

\begin{fdef}
	Eine CFG ist in der Chomsky Normal Form, wenn alle Regeln der Grammatik die folgende Form haben:
	\begin{itemize}
		\item $S \to \varepsilon$
		\item $A \to BC$
		\item $A \to a$
	\end{itemize}
	Wobei $S$ die Startvariable ist.
\end{fdef}

\subsubsection{CFG $\to$ CNF}
Um eine allgemeine Grammatik in die Chomsky Normal Form zu bringen kann man wie folgt vorgehen:
\begin{enumerate}
	\item Die Startvariable darf nur auf der linken Seite stehen. (evtl. eine neue Variable einführen)
	\item Entferne alle $\varepsilon$ Regeln, ausser von der Startvariable.
	\item Entferne alle Übergange der Form $A \to B$, wenn $A$ und $B$ Variablen sind
	\item Modifiziere die verbleibenden Regeln bis sie der CNF entsprechen
\end{enumerate}

\subsubsection{CFG $\to$ GPDA $\to$ PDA}
Alle CFGs können in PDAs umgewandelt werden. Wir betrachten generalisierte PDAs, um uns die Arbeit zu erleichtern.
\\

Ein Generalisierter PDA (GPDA) ist wie ein PDA, ausser das das oberste Stack Symbol durch einen ganzen String ersetzt werden kann und nicht nur durch ein einzelnes Symbol oder $\varepsilon$. Um vom GPDA zurück zu einem PDA zu kommen, müssen die String-Pushes nur noch durch einzelne einfache Pushes ersetzt werden.
\\

Vorgehen:
\begin{enumerate}
	\item Push das Markierungssymbol $\$$ und das Startsymbol auf den Stack.
	\item Wiederhole folgende Schritte beliebig oft:
		\begin{enumerate}
			\item Falls auf dem Stack zuoberst ein Variablen Symbol $A$ liegt, wähle nondeterministisch eine Regel von $A$ aus und ersetzt $A$ durch den String auf der rechten Seite der Regel.
			\item Falls auf dem Stack zuoberst ein Terminalsymbol $a$ liegt, dann lies das nächste Symbol vom Input und vergleiche die beiden.\\
				Falls sie gleich sind, mache weiter. Falls sie nicht gleich sind, verwerfe diesen Ausführungszweig.
			\item Falls auf dem Stack zuoberst das Markierungssymbol $\$$ liegt, gehe in den akzeptierenden Zustand.\\
				Falls der Input noch nicht fertig ist, so wir der PDA diesen Ausführungszweig trotzdem verwerfen.
		\end{enumerate}
\end{enumerate}


\subsubsection{PDA $\to$ CFG}
\begin{ftext}
	Theorem: Für jeden PDA gibt es eine CFG, die die gleiche Sprache akzeptiert
\end{ftext}
\\

Korollar: PDA $\approx$ CFG


Theo von Arx's avatar
Theo von Arx committed
161
162
163
% \subsection{Kontext-sensitive Grammatiken}
% Es existiert eine noch allgemeinere Form von Grammatiken. Im Allgemeinen ist eine nicht kontext-freie Grammatik eine Grammatik die auf der linken Seite einer Regel nicht nur eine Variable zulässt, sondern auch mehrere Variablen und Variablen gemischt mit Terminalsubstrings.
% \\
Theo von Arx's avatar
Theo von Arx committed
164

Theo von Arx's avatar
Theo von Arx committed
165
166
167
168
% \begin{bsp}
% 	\hspace*{0pt}\\
% 	\includegraphics[scale=0.34]{fig/cfg-csg-bsp}
% \end{bsp}
Theo von Arx's avatar
Theo von Arx committed
169
170


Theo von Arx's avatar
Theo von Arx committed
171
% \textbf{Kontext-sensitive Grammatiken} werden nicht kontext-freie Grammatiken genannt, deren Länge der linken Seite $\leq$ Länge der rechten Seite.
Theo von Arx's avatar
Theo von Arx committed
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193


\subsection{Tandem Pumping}
Analog zu regulären Sprachen gibt es ein Pumping Lemma für kontext-freie Sprachen. Die Idee ist, dass man kontext-freie Sprachen an zwei Stellen Pumpen kann. (aber nicht an mehr als zwei Stellen)
\\

\begin{ftext}
	Theorem: Sei $L$ eine kontext-freie Sprache, dann gibt es eine Zahl $p$ (die Tandem-Pumping Zahl), so dass alle Strings in L mit Länge $\geq p$ tandem-pumpbar innerhalb eines Substrings mit $p$ Buchstaben ist.
\end{ftext}
\\

In anderen Wort: Für alle $w \in L$ mit $|w| \geq p$ muss gelten:
\begin{itemize}
	\item $w = u v x y z$
	\item $|v y| \geq 1$							\hspace{140pt} pumpbare Bereiche sind nicht leer
	\item $|v x y| \leq p$							\hspace{133pt} Pumpen innerhalb eines Bereichs von $p$ Buchstaben
	\item $u v^i x y^i z \in L$ für alle $i \geq 0$							\hspace{60pt} Tandem-pumpen von $v$ und $y$.
\end{itemize}

Falls keine solche Zahl $p$ existiert, so ist die Sprache nicht kontext-frei.


Theo von Arx's avatar
Theo von Arx committed
194
195
196
197
198
% \subsection{Transducers}
% \begin{fdef}
% 	Ein endlicher Zustands-Transducer (FST) ist ein Type eines endliche Automaten, dessen Output ein String und nicht nur Akzeptieren oder Ablehnen ist.
% \end{fdef}
% \\
Theo von Arx's avatar
Theo von Arx committed
199

Theo von Arx's avatar
Theo von Arx committed
200
201
% Bei einem Transducer werden jedem Übergang zwei Symbole angeschrieben, das erste für den Input und das zweite für den Output. ($\varepsilon$ als Output bedeutet, das nichts ausgegeben werden soll)
% \\
Theo von Arx's avatar
Theo von Arx committed
202

Theo von Arx's avatar
Theo von Arx committed
203
204
205
206
% \begin{bsp}
% 	\hspace*{0pt}\\
% 	\includegraphics[scale=0.5]{fig/cfg-transducers}
% \end{bsp}
Theo von Arx's avatar
Theo von Arx committed
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229


\subsection{Touring Maschine (TM)}
Eine Touring Maschine ist ein Gerät mit einer endlichen Anzahl read-only Memory (Zustände) und einem unbegrenzten Anzahl read/write Tape-Memory. Es gibt keinen seperaten Input, der Input befindet sich auf dem Tape, wenn die TM startet.
\\

Definition: Eine Touring Maschine (TM) ist ein 7-Tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{acc}, q_{rej})$.
\begin{itemize}
	\item $Q, \Sigma$ und $q_0$ sind gleich wie bei einem FA.
	\item $q_{acc}$ und $q_{rej}$ sind die akzeptierenden und ablehnenden Zustände.
	\item $\Gamma$ ist das Tape Alphabet, das notwendigerweise das leere Symbol $\cdot$ enthält, als auch das Input Alphabet $\Sigma$
	\item $\delta$ ist wie folgt
		\[
			\delta: (Q - \{q_{acc}, q_{rej} \} ) \times \Gamma \to Q \times \Gamma \times \{L, R \}
		\]
	\item Bei einem nicht haltenden Zustand $p$, einem Tape Symbol $x$, so meint $\delta(p, x) = (q, y, D)$, dass die TM in den Zustand $q$ übergeht, $x$ durch $y$ ersetzt und der Tape Kopf sich in die Richtung $D$ (links oder recht) bewegt.
\end{itemize}

Ein String $x$ ist akzeptiert von $M$, wenn, nachdem $x$ auf das Tape geschrieben wurde und der Tape Kopf der TM auf die Position am weitesten links gesetzt und die TM laufen gelassen wurde, M schlussendlich den akzeptierenden Zustand erreicht.

\subsection{Decidability?, Halting-Problem?}


zrene's avatar
zrene committed
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
287
288
289
290
291
292
293
294
295
296
297
298
299
\subsection{Beispiele - Kontextfreie Grammatiken}
\begin{itemize}


	\item $L = \{w\ |\ $the length of w is odd $\}$ \\
	\textbf{Lösung}
	\\ $ V = {X,A} $\\
	$\Sigma = {0,1} $ \\
	$ R= \begin{cases}

      X \rightarrow XAX | A \\
      A \rightarrow 0 | 1
   \end{cases} \\
	 S = X
 $\\
 \vspace{0.1cm}
\hrule
\vspace{-0.1cm}

 \item $L = \{w\ |\ $contains more 1s than 0s $\}$ \\
 \textbf{Lösung}
 \\ $ V = {A} $\\
 $\Sigma = {0,1} $ \\
 $ R = \{ A \rightarrow AA\ |\ 1A0\ |\ 0A1\ |\ 1\ |\ \varepsilon\} $\\
 $	S = A1A $ \\
 \vspace{0.1cm}
\hrule
\vspace{-0.1cm}


 \item $L = \{w\#x\#y\#z\ |\ w,x,y,z \ \in \{ a,b \}^* $ and $|w| = |z| , |x| = |y| \}$ \\
 \textbf{Lösung}
 \\ $ V = {A,B,Y} $\\
 $\Sigma = {a,b,\#} $ \\
 $ R= \begin{cases}
		 A \rightarrow YAY\ |\ \#B\# \\
		 B \rightarrow YBY\ | \# \\
		 Y \rightarrow a|b
	\end{cases}$ \\
 $	S = A $\\
 \vspace{0.1cm}
\hrule
\vspace{-0.1cm}



  \item $L = \{w\#x\#y\#z\ |\ w,x,y,z \ \in \{ a,b \}^* $ and $|w| = |y| , |x| = |z| \}$ \\
  \textbf{Lösung}\\
	This Grammar is NOT context Free!\\
	\vspace{0.1cm}
\hrule
\vspace{-0.1cm}

			\item $ L = \{w | w $ starts and ends with the same symbol$\}$ \\
				$S_0 \rightarrow 0 S_1 0 \ | \ 1 S_1 1\ |\ \varepsilon $ \\
				$S_1 \rightarrow 0 S_1 \ | \ 1 S_1 |\ \varepsilon $\\

				\vspace{0.1cm}
\hrule
\vspace{-0.1cm}

			\item $ L = \{w | w=w^R $(w is a Palyndrom) $\}$ \\
				$S_0 \rightarrow 1S_01\ | \ 0S_0 0 \ |\ 0\ |\ 1\ | \varepsilon$\\


				      \vspace{0.1cm}
				      \hrule
				      \vspace{-0.1cm}

			\item $ L = \{w | $(w besitzt doppelt so viele 'a' wie 'b') $\}$ \\
zrene's avatar
zrene committed
300
				$S_0 \rightarrow S_1aab\ |\ aS_1ab \ | \ aaS_1b \ |\ aabS_1\ | \ S_1aba \ | \ aS_1ba \ | \ abS_1a \ |$\\
zrene's avatar
zrene committed
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
				.\ \ \ \ \ \ \ \ \ \ \ \  \ $ abaS_1 \ | \ S_1baa \ | \ bS_1aa \ | \ baS_1a \ | \ baaS_1    $ \\
				$S_1 \rightarrow S_0 | \varepsilon$\\
				\vspace{0.1cm}
\hrule
\vspace{-0.1cm}


			\item $ L = \{a^i b^j c^k | i=j + k \}$ \\
				$S_0 \rightarrow aS_0c \ |\ S_1$ \\
				$S_1 \rightarrow aS_1b\ |\ \varepsilon$ \\
				\vspace{0.1cm}
\hrule
\vspace{-0.1cm}


			\item $ L = \{a^i b^j c^k | j= i + k \}$ \\
				$S_0 \rightarrow aS_1bS_2\ |\ S_1bS_2c\ |\ \varepsilon$ \\
				$S_1 \rightarrow aS_1b\ |\ \varepsilon$ \\
				$S_2 \rightarrow bS_2c\ |\ \varepsilon$ \\
				\vspace{0.1cm}
\hrule
\vspace{-0.1cm}

zrene's avatar
zrene committed
324
325
326
327
328
329
330
331
332
%
% 			\item $ L = \{a^i b^j c^k | j= i + k \}$ \\
% 				$S_0 \rightarrow aS_1bS_2\ |\ S_1bS_2c\ |\ \varepsilon$ \\
% 				$S_1 \rightarrow aS_1b\ |\ \varepsilon$ \\
% 				$S_2 \rightarrow bS_2c\ |\ \varepsilon$ \\
% 				\\
% 				\vspace{0.1cm}
% \hrule
% \vspace{-0.1cm}
zrene's avatar
zrene committed
333
334
335
336


				\item $ L = \{a^i b^j c^k | j= i $ or $ j = k \}$ \\
				\begin{itemize}
zrene's avatar
zrene committed
337
					\item $L_1 =  \{a^i b^j c^k | j= i\}$ \\
zrene's avatar
zrene committed
338
339
340
341
						$S_1 \rightarrow aS_2bS_3\ |\ \varepsilon$ \\
						$S_2 \rightarrow aS_2b\ |\ \varepsilon$ \\
						$S_3 \rightarrow cS_3\ |\ \varepsilon$ \\

zrene's avatar
zrene committed
342
					\item $L_2 =  \{a^i b^j c^k | j= k\}$ \\
zrene's avatar
zrene committed
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
						$S_4 \rightarrow S_5bS_6c\ |\ \varepsilon$ \\
						$S_5 \rightarrow cS_5\ |\ \varepsilon$ \\
						$S_6 \rightarrow bS_6c\ |\ \varepsilon$ \\
				\end{itemize}
				$\rightarrow L = L_1\ |\ L_2 $ \\
				$\Rightarrow S_0 \rightarrow S_1\ | \ S_4$ \\

				\vspace{0.1cm}
\hrule
\vspace{-0.1cm}

				\item $ L = \{a^i b^j c^k | i \neq i + k \}$ \\
				$ \{a^i b^j c^k | i \neq i + k \} =  \{a^i b^j c^k | i > j + k \} \cup  \{a^i b^j c^k | i < j + k \}$ \\

				\begin{itemize}
					\item $L_1 =  \{a^i b^j c^k | i> j + k \}$ \\
						$S_1 \rightarrow aS_2$ \\
zrene's avatar
zrene committed
360
						$S_2 \rightarrow aS_2\ |\ aS_2c \ |\ S_3$ \\
zrene's avatar
zrene committed
361
362
						$S_3 \rightarrow aS_3 \ |\ aS_3b \ |\ \varepsilon$ \\

zrene's avatar
zrene committed
363
					\item $L_2 =  \{a^i b^j c^k | i < j + k\}$ \\
zrene's avatar
zrene committed
364
365
366
367
368
369
370
						$S_4 \rightarrow s_5c$ \\
						$S_5 \rightarrow s_5c \ |\ aS_5c \ |\ S_6 $ \\
						$S_6 \rightarrow S_6b\ |\ aS_6b \ |\ \varepsilon $ \\
				\end{itemize}
				$ L = \{a^i b^j c^k | i \neq i + k \}$ \\
				$\Rightarrow S_0 \rightarrow S_1| S_4$

Theo von Arx's avatar
Theo von Arx committed
371

zrene's avatar
zrene committed
372
373
374
375



\end{itemize}