421 \end{center}

   433 \end{center}\pause\bigskip

   422 

   434 

   423 \end{frame}}

   435 Why can't we just have an epsilon transition from the accepting states to the starting state?

   424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   436 

   425 

   437 \end{frame}}

   426 

   438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   427 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   439 

   428 \mode<presentation>{

   440 

   429 \begin{frame}[c]

   441 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   430 

   442 \mode<presentation>{

   431 \begin{textblock}{5}(1,1)

   443 \begin{frame}[c]

   444 \frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}

   445 

   446 

   447 \begin{textblock}{5}(1,2.5)

   435 \begin{textblock}{11}(6.5,3)

   451 \begin{textblock}{11}(6.5,4.5)

   455 

   471 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   456 

   472 \mode<presentation>{

   457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   473 \begin{frame}[c]

   458 \mode<presentation>{

   474 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}

   459 \begin{frame}[c]

   460 

   461 \begin{center}

   462 \includegraphics[scale=0.7]{pics/ch4.jpg}

   463 \end{center}

   464 

   465 \end{frame}}

   466 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   467 

   468 

   469 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   470 \mode<presentation>{

   471 \begin{frame}[c]

   472 \frametitle{\begin{tabular}{c}Languages\end{tabular}}

   475 a regular expression that recognises all its strings.\bigskip\bigskip\pause

   477 a regular expression that recognises all its strings.\bigskip\medskip

   476 

   478 

   477 \textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.}

   479 or equivalently\bigskip\medskip

   480 

   481 A language is \alert{regular} iff there exists

   482 a deterministic finite automaton that recognises all its strings.\bigskip\pause

   483 

   484 Why is every finite set of strings a regular language?

   485 \end{frame}}

   486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   487 

   488 

   489 

   490 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   491 \mode<presentation>{

   492 \begin{frame}[c]

   493 

   494 \begin{center}

   495 \includegraphics[scale=0.5]{pics/ch3.jpg}

   496 \end{center}

   497 

   498 \begin{center}

   499 \includegraphics[scale=0.5]{pics/ch4.jpg}\\

   500 minimal automaton

   501 \end{center}

   502 

   503 \end{frame}}

   504 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   505 

   506 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   507 \mode<presentation>{

   508 \begin{frame}[c]

   509 

   510 Given the function 

   511 

   512 \begin{center}

   513 \bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}

   514 $rev(\varnothing)$   & $\dn$ & $\varnothing$\\

   515 $rev(\epsilon)$         & $\dn$ & $\epsilon$\\

   516 $rev(c)$                      & $\dn$ & $c$\\

   517 $rev(r_1 + r_2)$        & $\dn$ & $rev(r_1) + rev(r_2)$\\

   518 $rev(r_1 \cdot r_2)$  & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\

   519 $rev(r^*)$                   & $\dn$ & $rev(r)^*$\\

   520 \end{tabular}}

   521 \end{center}

   522 

   523 

   524 and the set

   525 

   526 \begin{center}

   527 \bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$}

   528 \end{center}

   529 

   530 prove whether

   531 

   532 \begin{center}

   533 \bl{$L(rev(r)) = Rev (L(r))$}

   534 \end{center}

   535 

   536 \end{frame}}

   537 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   538 

   539 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   540 \mode<presentation>{

   541 \begin{frame}[c]

   542 

   543 \begin{itemize}

   544 \item The star-case in our proof about the matcher needs the following lemma

   545 \begin{center}

   546 \bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$}

   547 \end{center}

   548 \end{itemize}\bigskip\bigskip

   549 

   550 \begin{itemize}

   551 \item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip

   552 \item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B}

   553 

   554 \end{itemize}

   555 

   498 

   576 Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only.

   499 

   577 (a) Find a regular expression that recognises the two strings \bl{$ab$} and \bl{$ac$}. (b)

   500 \begin{itemize}

   578 Find a regular expression that matches all strings \emph{except} these two strings.

   501 \item The star-case in our proof needs the following lemma

   579 Note, you can only use regular expressions of the form 

   502 \begin{center}

   580 \begin{center}

   503 \bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$}

   581 \bl{$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$}

   504 \end{center}

   582 \end{center}

   505 \end{itemize}\bigskip\bigskip

   506 

   507 

   508 

   509 \begin{itemize}

   510 \item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip

   511 \item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B}

   512 

   513 \end{itemize}