--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/slides/slides04.tex Sat Jun 15 09:23:18 2013 -0400
@@ -0,0 +1,612 @@
+\documentclass[dvipsnames,14pt,t]{beamer}
+\usepackage{beamerthemeplainculight}
+\usepackage[T1]{fontenc}
+\usepackage[latin1]{inputenc}
+\usepackage{mathpartir}
+\usepackage[absolute,overlay]{textpos}
+\usepackage{ifthen}
+\usepackage{tikz}
+\usepackage{pgf}
+\usepackage{calc}
+\usepackage{ulem}
+\usepackage{courier}
+\usepackage{listings}
+\renewcommand{\uline}[1]{#1}
+\usetikzlibrary{arrows}
+\usetikzlibrary{automata}
+\usetikzlibrary{shapes}
+\usetikzlibrary{shadows}
+\usetikzlibrary{positioning}
+\usetikzlibrary{calc}
+\usepackage{graphicx}
+
+\definecolor{javared}{rgb}{0.6,0,0} % for strings
+\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
+\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
+\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
+
+\lstset{language=Java,
+ basicstyle=\ttfamily,
+ keywordstyle=\color{javapurple}\bfseries,
+ stringstyle=\color{javagreen},
+ commentstyle=\color{javagreen},
+ morecomment=[s][\color{javadocblue}]{/**}{*/},
+ numbers=left,
+ numberstyle=\tiny\color{black},
+ stepnumber=1,
+ numbersep=10pt,
+ tabsize=2,
+ showspaces=false,
+ showstringspaces=false}
+
+\lstdefinelanguage{scala}{
+ morekeywords={abstract,case,catch,class,def,%
+ do,else,extends,false,final,finally,%
+ for,if,implicit,import,match,mixin,%
+ new,null,object,override,package,%
+ private,protected,requires,return,sealed,%
+ super,this,throw,trait,true,try,%
+ type,val,var,while,with,yield},
+ otherkeywords={=>,<-,<\%,<:,>:,\#,@},
+ sensitive=true,
+ morecomment=[l]{//},
+ morecomment=[n]{/*}{*/},
+ morestring=[b]",
+ morestring=[b]',
+ morestring=[b]"""
+}
+
+\lstset{language=Scala,
+ basicstyle=\ttfamily,
+ keywordstyle=\color{javapurple}\bfseries,
+ stringstyle=\color{javagreen},
+ commentstyle=\color{javagreen},
+ morecomment=[s][\color{javadocblue}]{/**}{*/},
+ numbers=left,
+ numberstyle=\tiny\color{black},
+ stepnumber=1,
+ numbersep=10pt,
+ tabsize=2,
+ showspaces=false,
+ showstringspaces=false}
+
+% beamer stuff
+\renewcommand{\slidecaption}{AFL 04, King's College London, 17.~October 2012}
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+
+\begin{document}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}<1>[t]
+\frametitle{%
+ \begin{tabular}{@ {}c@ {}}
+ \\[-3mm]
+ \LARGE Automata and \\[-2mm]
+ \LARGE Formal Languages (4)\\[3mm]
+ \end{tabular}}
+
+ \normalsize
+ \begin{center}
+ \begin{tabular}{ll}
+ Email: & christian.urban at kcl.ac.uk\\
+ Of$\!$fice: & S1.27 (1st floor Strand Building)\\
+ Slides: & KEATS (also home work is there)\\
+ \end{tabular}
+ \end{center}
+
+
+\end{frame}}
+ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Last Week\end{tabular}}
+
+Last week I showed you\bigskip
+
+\begin{itemize}
+\item a tokenizer taking a list of regular expressions\bigskip
+
+\item tokenization identifies lexeme in an input stream of characters (or string)
+and cathegorizes them into tokens
+
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Two Rules\end{tabular}}
+
+\begin{itemize}
+\item Longest match rule (maximal munch rule): The
+longest initial substring matched by any regular expression is taken
+as next token.\bigskip
+
+\item Rule priority:
+For a particular longest initial substring, the first regular
+expression that can match determines the token.
+
+\end{itemize}
+
+%\url{http://www.technologyreview.com/tr10/?year=2011}
+
+%finite deterministic automata/ nondeterministic automaton
+
+%\item problem with infix operations, for example i-12
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\mode<presentation>{
+\begin{frame}[t]
+
+\begin{center}
+\texttt{"if true then then 42 else +"}
+\end{center}
+
+
+\begin{tabular}{@{}l}
+KEYWORD: \\
+\hspace{5mm}\texttt{"if"}, \texttt{"then"}, \texttt{"else"},\\
+WHITESPACE:\\
+\hspace{5mm}\texttt{" "}, \texttt{"$\backslash$n"},\\
+IDENT:\\
+\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + \texttt{"\_"})$^*$\\
+NUM:\\
+\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\
+OP:\\
+\hspace{5mm}\texttt{"+"}\\
+COMMENT:\\
+\hspace{5mm}\texttt{"$\slash$*"} $\cdot$ (ALL$^*$ $\cdot$ \texttt{"*$\slash$"} $\cdot$ ALL$^*$) $\cdot$ \texttt{"*$\slash$"}
+\end{tabular}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+
+\begin{center}
+\texttt{"if true then then 42 else +"}
+\end{center}
+
+\only<1>{
+\small\begin{tabular}{l}
+KEYWORD(if),\\
+WHITESPACE,\\
+IDENT(true),\\
+WHITESPACE,\\
+KEYWORD(then),\\
+WHITESPACE,\\
+KEYWORD(then),\\
+WHITESPACE,\\
+NUM(42),\\
+WHITESPACE,\\
+KEYWORD(else),\\
+WHITESPACE,\\
+OP(+)
+\end{tabular}}
+
+\only<2>{
+\small\begin{tabular}{l}
+KEYWORD(if),\\
+IDENT(true),\\
+KEYWORD(then),\\
+KEYWORD(then),\\
+NUM(42),\\
+KEYWORD(else),\\
+OP(+)
+\end{tabular}}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+
+There is one small problem with the tokenizer. How should we
+tokenize:
+
+\begin{center}
+\texttt{"x - 3"}
+\end{center}
+
+\begin{tabular}{@{}l}
+OP:\\
+\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\
+NUM:\\
+\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\
+NUMBER:\\
+\hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\
+\end{tabular}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Negation\end{tabular}}
+
+Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only.
+Find a regular expression that matches all strings \emph{except} \bl{ab}, \bl{ac} and \bl{cba}.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}}
+
+A deterministic finite automaton consists of:
+
+\begin{itemize}
+\item a finite set of states
+\item one of these states is the start state
+\item some states are accepting states, and
+\item there is transition function\medskip
+
+\small
+which takes a state and a character as arguments and produces a new state\smallskip\\
+this function might not always be defined everywhere
+\end{itemize}
+
+\begin{center}
+\bl{$A(Q, q_0, F, \delta)$}
+\end{center}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\includegraphics[scale=0.7]{pics/ch3.jpg}
+\end{center}\pause
+
+\begin{itemize}
+\item start can be an accepting state
+\item it is possible that there is no accepting state
+\item all states might be accepting (but does not necessarily mean all strings are accepted)
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\includegraphics[scale=0.7]{pics/ch3.jpg}
+\end{center}
+
+for this automaton \bl{$\delta$} is the function\\
+
+\begin{center}
+\begin{tabular}{lll}
+\bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\
+\bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\
+\end{tabular}\ldots
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Accepting a String\end{tabular}}
+
+Given
+
+\begin{center}
+\bl{$A(Q, q_0, F, \delta)$}
+\end{center}
+
+you can define
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$\hat{\delta}(q, \texttt{""}) = q$}\\
+\bl{$\hat{\delta}(q, c::s) = \hat{\delta}(\delta(q, c), s)$}\\
+\end{tabular}
+\end{center}\pause
+
+Whether a string \bl{$s$} is accepted by \bl{$A$}?
+
+\begin{center}
+\hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$}
+\end{center}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}}
+
+A non-deterministic finite automaton consists again of:
+
+\begin{itemize}
+\item a finite set of states
+\item one of these states is the start state
+\item some states are accepting states, and
+\item there is transition \alert{relation}\medskip
+\end{itemize}
+
+
+\begin{center}
+\begin{tabular}{c}
+\bl{(q$_1$, a) $\rightarrow$ q$_2$}\\
+\bl{(q$_1$, a) $\rightarrow$ q$_3$}\\
+\end{tabular}
+\hspace{10mm}
+\begin{tabular}{c}
+\bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\includegraphics[scale=0.7]{pics/ch5.jpg}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\begin{tabular}[b]{ll}
+\bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\
+\bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\
+\bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\begin{tabular}[t]{ll}
+\bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\begin{tabular}[t]{ll}
+\bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\begin{tabular}[b]{ll}
+\bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\
+\end{tabular}
+\end{center}\pause\bigskip
+
+Why can't we just have an epsilon transition from the accepting states to the starting state?
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}
+
+
+\begin{textblock}{5}(1,2.5)
+\includegraphics[scale=0.5]{pics/ch5.jpg}
+\end{textblock}
+
+\begin{textblock}{11}(6.5,4.5)
+\begin{tabular}{r|cl}
+& a & b\\
+\hline
+$\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\
+$\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\
+$\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\
+$\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\
+$\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\
+$\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\
+$\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\
+\onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\
+\end{tabular}
+\end{textblock}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
+
+A language is \alert{regular} iff there exists
+a regular expression that recognises all its strings.\bigskip\medskip
+
+or equivalently\bigskip\medskip
+
+A language is \alert{regular} iff there exists
+a deterministic finite automaton that recognises all its strings.\bigskip\pause
+
+Why is every finite set of strings a regular language?
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\includegraphics[scale=0.5]{pics/ch3.jpg}
+\end{center}
+
+\begin{center}
+\includegraphics[scale=0.5]{pics/ch4.jpg}\\
+minimal automaton
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{enumerate}
+\item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p}
+\item Mark all pairs that accepting and non-accepting states
+\item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether
+\begin{center}
+\bl{($\delta$(q,c), $\delta$(p,c))}
+\end{center}
+are marked. If yes, then also mark \bl{(q, p)}
+\item Repeat last step until no chance.
+\item All unmarked pairs can be merged.
+\end{enumerate}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+Given the function
+
+\begin{center}
+\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$rev(\varnothing)$ & $\dn$ & $\varnothing$\\
+$rev(\epsilon)$ & $\dn$ & $\epsilon$\\
+$rev(c)$ & $\dn$ & $c$\\
+$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
+$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
+$rev(r^*)$ & $\dn$ & $rev(r)^*$\\
+\end{tabular}}
+\end{center}
+
+
+and the set
+
+\begin{center}
+\bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$}
+\end{center}
+
+prove whether
+
+\begin{center}
+\bl{$L(rev(r)) = Rev (L(r))$}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{itemize}
+\item The star-case in our proof about the matcher needs the following lemma
+\begin{center}
+\bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$}
+\end{center}
+\end{itemize}\bigskip\bigskip
+
+\begin{itemize}
+\item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip
+\item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B}
+
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{itemize}
+\item Assuming you have the alphabet \bl{\{a, b, c\}}\bigskip
+\item Give a regular expression that can recognise all strings that have at least one \bl{b}.
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+``I hate coding. I do not want to look at code.''
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
+