163 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
163 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
164 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
164 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
165 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
165 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
166 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
166 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
167 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
167 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
168 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause |
168 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\ |
169 |
169 |
170 \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
170 \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
171 \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\ |
171 \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\ |
172 \end{tabular} |
172 \end{tabular} |
173 \end{center} |
173 \end{center} |
358 \frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}} |
358 \frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}} |
359 |
359 |
360 \begin{itemize} |
360 \begin{itemize} |
361 \item \bl{$\sim{}r$} \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip |
361 \item \bl{$\sim{}r$} \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip |
362 \item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip |
362 \item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip |
363 \item \bl{$nullable (r) \dn not (nullable(r))$}\medskip |
363 \item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip |
364 \item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$} |
364 \item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$} |
365 \end{itemize}\bigskip\pause |
365 \end{itemize}\bigskip\pause |
366 |
366 |
367 Used often for comments: |
367 Used often for recognising comments: |
368 |
368 |
369 \[ |
369 \[ |
370 \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /} |
370 \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /} |
371 \] |
371 \] |
372 |
372 |
378 \mode<presentation>{ |
378 \mode<presentation>{ |
379 \begin{frame}[c] |
379 \begin{frame}[c] |
380 \frametitle{\begin{tabular}{c}Negation\end{tabular}} |
380 \frametitle{\begin{tabular}{c}Negation\end{tabular}} |
381 |
381 |
382 Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only. |
382 Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only. |
383 Find a regular expression that matches all strings \emph{except} \bl{ab}, \bl{ac} and \bl{cba}. |
383 Find a regular expression that matches all strings \emph{except} \bl{ab} and \bl{ac}. |
384 |
384 |
385 \end{frame}} |
385 \end{frame}} |
386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
387 |
387 |
388 |
388 |
408 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
408 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
409 \mode<presentation>{ |
409 \mode<presentation>{ |
410 \begin{frame}[c] |
410 \begin{frame}[c] |
411 \frametitle{\begin{tabular}{c}Automata\end{tabular}} |
411 \frametitle{\begin{tabular}{c}Automata\end{tabular}} |
412 |
412 |
413 A deterministic finite automaton consists of: |
413 A \alert{deterministic finite automaton} consists of: |
414 |
414 |
415 \begin{itemize} |
415 \begin{itemize} |
416 \item a set of states |
416 \item a set of states |
417 \item one of these states is the start state |
417 \item one of these states is the start state |
418 \item some states are accepting states, and |
418 \item some states are accepting states, and |
419 \item there is transition function\medskip |
419 \item there is transition function\medskip |
420 |
420 |
421 \small |
421 \small |
422 which takes a state as argument and a character and produces a new state\smallskip\\ |
422 which takes a state as argument and a character and produces a new state\smallskip\\ |
423 this function might not always be defined |
423 this function might not be everywhere defined |
424 \end{itemize} |
|
425 |
|
426 \end{frame}} |
|
427 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
428 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
429 \mode<presentation>{ |
|
430 \begin{frame}[c] |
|
431 \frametitle{\begin{tabular}{c}Automata\end{tabular}} |
|
432 |
|
433 A deterministic finite automaton consists of: |
|
434 |
|
435 \begin{itemize} |
|
436 \item a set of states |
|
437 \item one of these states is the start state |
|
438 \item some states are accepting states, and |
|
439 \item there is transition function\medskip |
|
440 |
|
441 \small |
|
442 which takes a state as argument and a character and produces a new state\smallskip\\ |
|
443 this function might not always be defined |
|
444 \end{itemize} |
424 \end{itemize} |
445 |
425 |
446 \begin{center} |
426 \begin{center} |
447 \bl{$A(Q, q_0, F, \delta)$} |
427 \bl{$A(Q, q_0, F, \delta)$} |
448 \end{center} |
428 \end{center} |
548 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
528 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
549 |
529 |
550 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
530 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
551 \mode<presentation>{ |
531 \mode<presentation>{ |
552 \begin{frame}[c] |
532 \begin{frame}[c] |
553 |
533 \frametitle{An NFA} |
554 \begin{center} |
534 |
555 \includegraphics[scale=0.7]{pics/ch5.jpg} |
535 \begin{center} |
|
536 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
|
537 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
|
538 \node[state,initial] (q_0) {$q_0$}; |
|
539 \node[state] (q_1) [above=of q_0] {$q_1$}; |
|
540 \node[state, accepting] (q_2) [below=of q_0] {$q_2$}; |
|
541 \path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1); |
|
542 \path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2); |
|
543 \path[->] (q_0) edge [loop right] node {\alert{$a$}} (); |
|
544 \path[->] (q_1) edge [loop above] node {\alert{$a$}} (); |
|
545 \path[->] (q_2) edge [loop below] node {\alert{$b$}} (); |
|
546 \end{tikzpicture} |
556 \end{center} |
547 \end{center} |
557 |
548 |
558 |
549 |
559 \end{frame}} |
550 \end{frame}} |
560 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
551 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
620 \mode<presentation>{ |
611 \mode<presentation>{ |
621 \begin{frame}[c] |
612 \begin{frame}[c] |
622 \frametitle{\begin{tabular}{c}Subset Construction\end{tabular}} |
613 \frametitle{\begin{tabular}{c}Subset Construction\end{tabular}} |
623 |
614 |
624 |
615 |
625 \begin{textblock}{5}(1,2.5) |
616 \begin{textblock}{5}(1,1) |
626 \includegraphics[scale=0.5]{pics/ch5.jpg} |
617 \begin{center} |
|
618 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, |
|
619 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
|
620 \node[state,initial] (q_0) {$q_0$}; |
|
621 \node[state] (q_1) [above=of q_0] {$q_1$}; |
|
622 \node[state, accepting] (q_2) [below=of q_0] {$q_2$}; |
|
623 \path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1); |
|
624 \path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2); |
|
625 \path[->] (q_0) edge [loop right] node {\alert{$a$}} (); |
|
626 \path[->] (q_1) edge [loop above] node {\alert{$a$}} (); |
|
627 \path[->] (q_2) edge [loop below] node {\alert{$b$}} (); |
|
628 \end{tikzpicture} |
|
629 \end{center} |
627 \end{textblock} |
630 \end{textblock} |
628 |
631 |
629 \begin{textblock}{11}(6.5,4.5) |
632 \begin{textblock}{11}(6.5,4.5) |
630 \begin{tabular}{r|cl} |
633 \begin{tabular}{r|cl} |
631 & a & b\\ |
634 & a & b\\ |
686 \mode<presentation>{ |
689 \mode<presentation>{ |
687 \begin{frame}[c] |
690 \begin{frame}[c] |
688 |
691 |
689 \begin{enumerate} |
692 \begin{enumerate} |
690 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
693 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
691 \item Mark all pairs that accepting and non-accepting states |
694 \item Mark all pairs that are accepting and non-accepting states |
692 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
695 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
693 \begin{center} |
696 \begin{center} |
694 \bl{($\delta$(q,c), $\delta$(p,c))} |
697 \bl{($\delta$(q,c), $\delta$(p,c))} |
695 \end{center} |
698 \end{center} |
696 are marked. If yes, then also mark \bl{(q, p)} |
699 are marked. If yes, then also mark \bl{(q, p)} |