363 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   364 \mode<presentation>{

   365 \begin{frame}[t]

   366 \frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}}

   367 

   368 Remember their inductive definition:\\[5cm]

   369 

   370 \begin{textblock}{6}(5,5)

   371   \begin{tabular}{@ {}rrl}

   372   \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}\\

   373          & \bl{$\mid$} & \bl{$\epsilon$}       \\

   374          & \bl{$\mid$} & \bl{c}                        \\

   375          & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$}\\

   376          & \bl{$\mid$} & \bl{r$_1$ + r$_2$}  \\

   377          & \bl{$\mid$} & \bl{r$^*$}                  \\

   378   \end{tabular}

   379   \end{textblock}

   380 

   381 If we want to prove something, say a property \bl{$P$(r)}, for all regular expressions \bl{r} then \ldots

   382 

   383 \end{frame}}

   384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   385 

   386 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   387 \mode<presentation>{

   388 \begin{frame}[c]

   389 \frametitle{\begin{tabular}{c}Proofs about Rexp (2)\end{tabular}}

   390 

   391 \begin{itemize}

   392 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip

   393 \item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already

   394 holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip

   395 \item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already

   396 holds for \bl{r$_1$} and \bl{r$_2$}.

   397 \item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already

   398 holds for \bl{r}.

   399 \end{itemize}

   400 

   401 \end{frame}}

   402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   403 

   404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   405 \mode<presentation>{

   406 \begin{frame}[c]

   407 \frametitle{\begin{tabular}{c}Proofs about Rexp (3)\end{tabular}}

   408 

   409 Assume \bl{$P(r)$} is the property:

   410 

   411 \begin{center}

   412 \bl{nullable(r)} if and only if \bl{"" $\in$ $L$(r)}

   413 \end{center}

   414 

   415 \end{frame}}

   416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   417 

   418 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   419 \mode<presentation>{

   420 \begin{frame}[c]

   421 \frametitle{\begin{tabular}{c}Proofs about Strings\end{tabular}}

   422 

   423 If we want to prove something, say a property \bl{$P$(s)}, for all strings \bl{s} then \ldots\bigskip

   424 

   425 \begin{itemize}

   426 \item \bl{$P$} holds for the empty string, and\medskip

   427 \item \bl{$P$} holds for the string \bl{c::s} under the assumption that \bl{$P$}

   428 already holds for \bl{s}

   429 \end{itemize}

   430 \end{frame}}

   431 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   432 

   433 

   434 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   435 \mode<presentation>{

   436 \begin{frame}[c]

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

   438 

   439 A language (set of strings) is \alert{regular} iff there exists

   440 a regular expression that recognises all its strings.

   441 

   442 \end{frame}}

   443 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   444 

   445 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   446 \mode<presentation>{

   447 \begin{frame}[c]

   448 \frametitle{\begin{tabular}{c}Automata\end{tabular}}

   449 

   450 A deterministic finite automaton consists of:

   451 

   452 \begin{itemize}

   453 \item a set of states

   454 \item one of these states is the start state

   455 \item some states are accepting states, and

   456 \item there is transition function\medskip 

   457 

   458 \small

   459 which takes a state as argument and a character and produces a new state\smallskip\\

   460 this function might not always be defined

   461 \end{itemize}

   462 

   463 \end{frame}}

   464 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   465