141 %\item problem with infix operations, for example i-12 |
141 %\item problem with infix operations, for example i-12 |
142 |
142 |
143 |
143 |
144 \end{frame}} |
144 \end{frame}} |
145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
147 |
|
148 \mode<presentation>{ |
|
149 \begin{frame}[t] |
|
150 |
|
151 \begin{center} |
|
152 \texttt{"if true then then 42 else +"} |
|
153 \end{center} |
|
154 |
|
155 |
|
156 \begin{tabular}{@{}l} |
|
157 KEYWORD: \\ |
|
158 \hspace{5mm}\texttt{"if"}, \texttt{"then"}, \texttt{"else"},\\ |
|
159 WHITESPACE:\\ |
|
160 \hspace{5mm}\texttt{" "}, \texttt{"$\backslash$n"},\\ |
|
161 IDENT:\\ |
|
162 \hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + \texttt{"\_"})$^*$\\ |
|
163 NUM:\\ |
|
164 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\ |
|
165 OP:\\ |
|
166 \hspace{5mm}\texttt{"+"}\\ |
|
167 COMMENT:\\ |
|
168 \hspace{5mm}\texttt{"$\slash$*"} $\cdot$ (ALL$^*$ $\cdot$ \texttt{"*$\slash$"} $\cdot$ ALL$^*$) $\cdot$ \texttt{"*$\slash$"} |
|
169 \end{tabular} |
|
170 |
|
171 \end{frame}} |
|
172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
146 |
173 |
147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
148 \mode<presentation>{ |
175 \mode<presentation>{ |
149 \begin{frame}[t] |
176 \begin{frame}[t] |
150 |
177 |
230 \mode<presentation>{ |
265 \mode<presentation>{ |
231 \begin{frame}[c] |
266 \begin{frame}[c] |
232 |
267 |
233 \begin{center} |
268 \begin{center} |
234 \includegraphics[scale=0.7]{pics/ch3.jpg} |
269 \includegraphics[scale=0.7]{pics/ch3.jpg} |
235 \end{center} |
270 \end{center}\pause |
236 |
271 |
237 \end{frame}} |
272 \begin{itemize} |
238 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
273 \item start can be an accepting state |
|
274 \item there is no accepting state |
|
275 \item all states are accepting |
|
276 \end{itemize} |
|
277 |
|
278 \end{frame}} |
|
279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
280 |
|
281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
282 \mode<presentation>{ |
|
283 \begin{frame}[c] |
|
284 |
|
285 \begin{center} |
|
286 \includegraphics[scale=0.7]{pics/ch3.jpg} |
|
287 \end{center} |
|
288 |
|
289 for this automaton \bl{$\delta$} is the function\\ |
|
290 |
|
291 \begin{center} |
|
292 \begin{tabular}{lll} |
|
293 \bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\ |
|
294 \bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\ |
|
295 \end{tabular}\ldots |
|
296 \end{center} |
|
297 |
|
298 \end{frame}} |
|
299 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
300 |
|
301 |
239 |
302 |
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
303 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
241 \mode<presentation>{ |
304 \mode<presentation>{ |
242 \begin{frame}[t] |
305 \begin{frame}[t] |
243 \frametitle{\begin{tabular}{c}Accepting a String\end{tabular}} |
306 \frametitle{\begin{tabular}{c}Accepting a String\end{tabular}} |
244 |
307 |
|
308 Given |
|
309 |
245 \begin{center} |
310 \begin{center} |
246 \bl{$A(Q, q_0, F, \delta)$} |
311 \bl{$A(Q, q_0, F, \delta)$} |
247 \end{center}\bigskip |
312 \end{center} |
|
313 |
|
314 you can define |
248 |
315 |
249 \begin{center} |
316 \begin{center} |
250 \begin{tabular}{l} |
317 \begin{tabular}{l} |
251 \bl{$\hat{\delta}(\texttt{""}, q) = q$}\\ |
318 \bl{$\hat{\delta}(q, \texttt{""}) = q$}\\ |
252 \bl{$\hat{\delta}(c::s, q) = \hat{\delta}(s, \delta(c, q))$}\\ |
319 \bl{$\hat{\delta}(q, c::s) = \hat{\delta}(\delta(q, c), s)$}\\ |
253 \end{tabular} |
320 \end{tabular} |
254 \end{center}\bigskip\pause |
321 \end{center}\pause |
255 |
322 |
256 \begin{center} |
323 Whether a string \bl{$s$} is accepted by \bl{$A$}? |
257 Accepting? \hspace{5mm}\bl{$\hat{\delta}(s, q_0) \in F$} |
324 |
258 \end{center} |
325 \begin{center} |
259 \end{frame}} |
326 \hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$} |
260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
327 \end{center} |
|
328 \end{frame}} |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 |
|
331 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
332 \mode<presentation>{ |
|
333 \begin{frame}[c] |
|
334 \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} |
|
335 |
|
336 A non-deterministic finite automaton consists again of: |
|
337 |
|
338 \begin{itemize} |
|
339 \item a finite set of states |
|
340 \item one of these states is the start state |
|
341 \item some states are accepting states, and |
|
342 \item there is transition \alert{relation}\medskip |
|
343 \end{itemize} |
|
344 |
|
345 |
|
346 \begin{center} |
|
347 \begin{tabular}{c} |
|
348 \bl{(q$_1$, a) $\rightarrow$ q$_2$}\\ |
|
349 \bl{(q$_1$, a) $\rightarrow$ q$_3$}\\ |
|
350 \end{tabular} |
|
351 \hspace{10mm} |
|
352 \begin{tabular}{c} |
|
353 \bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\ |
|
354 \end{tabular} |
|
355 \end{center} |
|
356 |
|
357 \end{frame}} |
|
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
359 |
|
360 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
361 \mode<presentation>{ |
|
362 \begin{frame}[c] |
|
363 |
|
364 \begin{center} |
|
365 \includegraphics[scale=0.7]{pics/ch5.jpg} |
|
366 \end{center} |
|
367 |
|
368 \end{frame}} |
|
369 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
370 |
|
371 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
372 \mode<presentation>{ |
|
373 \begin{frame}[c] |
|
374 |
|
375 \begin{center} |
|
376 \begin{tabular}[b]{ll} |
|
377 \bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\ |
|
378 \bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\ |
|
379 \bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\ |
|
380 \end{tabular} |
|
381 \end{center} |
|
382 |
|
383 \end{frame}} |
|
384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
385 |
|
386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
387 \mode<presentation>{ |
|
388 \begin{frame}[c] |
|
389 |
|
390 \begin{center} |
|
391 \begin{tabular}[t]{ll} |
|
392 \bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\ |
|
393 \end{tabular} |
|
394 \end{center} |
|
395 |
|
396 \end{frame}} |
|
397 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
398 |
|
399 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
400 \mode<presentation>{ |
|
401 \begin{frame}[c] |
|
402 |
|
403 \begin{center} |
|
404 \begin{tabular}[t]{ll} |
|
405 \bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\ |
|
406 \end{tabular} |
|
407 \end{center} |
|
408 |
|
409 \end{frame}} |
|
410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
411 |
|
412 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
413 \mode<presentation>{ |
|
414 \begin{frame}[c] |
|
415 |
|
416 \begin{center} |
|
417 \begin{tabular}[b]{ll} |
|
418 \bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\ |
|
419 \end{tabular} |
|
420 \end{center} |
|
421 |
|
422 \end{frame}} |
|
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
424 |
|
425 |
|
426 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
427 \mode<presentation>{ |
|
428 \begin{frame}[c] |
|
429 |
|
430 \begin{center} |
|
431 \includegraphics[scale=0.5]{pics/ch5.jpg} |
|
432 \end{center} |
|
433 |
|
434 \end{frame}} |
|
435 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
436 |
|
437 |
|
438 |
261 |
439 |
262 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
440 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
263 \mode<presentation>{ |
441 \mode<presentation>{ |
264 \begin{frame}[c] |
442 \begin{frame}[c] |
265 |
443 |