equal
deleted
inserted
replaced
281 \includegraphics[scale=0.7]{pics/ch3.jpg} |
281 \includegraphics[scale=0.7]{pics/ch3.jpg} |
282 \end{center}\pause |
282 \end{center}\pause |
283 |
283 |
284 \begin{itemize} |
284 \begin{itemize} |
285 \item start can be an accepting state |
285 \item start can be an accepting state |
286 \item there is no accepting state |
286 \item it is possible that there is no accepting state |
287 \item all states are accepting |
287 \item all states might be accepting (but does not necessarily mean all strings are accepted) |
288 \end{itemize} |
288 \end{itemize} |
289 |
289 |
290 \end{frame}} |
290 \end{frame}} |
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
291 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
292 |
292 |
501 \end{center} |
501 \end{center} |
502 |
502 |
503 \end{frame}} |
503 \end{frame}} |
504 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
504 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
505 |
505 |
|
506 |
|
507 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
508 \mode<presentation>{ |
|
509 \begin{frame}[c] |
|
510 |
|
511 \begin{enumerate} |
|
512 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
513 \item Mark all pairs that accepting and non-accepting states |
|
514 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
515 \begin{center} |
|
516 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
517 \end{center} |
|
518 are marked. If yes, then also mark bl{(q, p)} |
|
519 \item Repeat last step until no chance. |
|
520 \item All unmarked pairs can be merged. |
|
521 \end{enumerate} |
|
522 |
|
523 \end{frame}} |
|
524 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
525 |
|
526 |
|
527 |
506 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
528 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
507 \mode<presentation>{ |
529 \mode<presentation>{ |
508 \begin{frame}[c] |
530 \begin{frame}[c] |
509 |
531 |
510 Given the function |
532 Given the function |
567 \end{itemize} |
589 \end{itemize} |
568 |
590 |
569 \end{frame}} |
591 \end{frame}} |
570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
592 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
571 |
593 |
572 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
594 |
573 \mode<presentation>{ |
|
574 \begin{frame}[c] |
|
575 |
|
576 Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only. |
|
577 (a) Find a regular expression that recognises the two strings \bl{$ab$} and \bl{$ac$}. (b) |
|
578 Find a regular expression that matches all strings \emph{except} these two strings. |
|
579 Note, you can only use regular expressions of the form |
|
580 \begin{center} |
|
581 \bl{$r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$} |
|
582 \end{center} |
|
583 |
|
584 \end{frame}} |
|
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
586 |
595 |
587 |
596 |
588 \end{document} |
597 \end{document} |
589 |
598 |
590 %%% Local Variables: |
599 %%% Local Variables: |