\documentclass[dvipsnames,14pt,t]{beamer}+ −
\usepackage{beamerthemeplaincu}+ −
%%\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+ −
\makeatletter+ −
\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}+ −
\@empty\z@\@empty+ −
\makeatother+ −
+ − \lstset{language=Java,+ −
basicstyle=\consolas,+ −
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=\consolas,+ −
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 03, King's College London, 9.~October 2013}+ −
\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 (3)\\[3mm] + −
\end{tabular}}+ −
+ − %\begin{center}+ −
%\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}+ −
%\includegraphics[scale=0.31]{pics/ante2.jpg}\\+ −
%\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}+ −
%\end{center}+ −
+ − \normalsize+ −
\begin{center}+ −
\begin{tabular}{lp{8cm}}+ −
Email: & christian.urban at kcl.ac.uk\\+ −
Office: & S1.27 (1st floor Strand Building)\\+ −
Slides: & KEATS (also home work and coursework is there)\\+ −
\end{tabular}+ −
\end{center}+ −
+ − + − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}+ −
+ − In programming languages they are often used to recognise:\medskip+ −
+ − \begin{itemize}+ −
\item symbols, digits+ −
\item identifiers+ −
\item numbers (non-leading zeros)+ −
\item keywords+ −
\item comments+ −
\end{itemize}\bigskip+ −
+ − + − \mbox{}\hfill\bl{\url{http://www.regexper.com}}+ −
\end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − + − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}Last Week\end{tabular}}+ −
+ − Last week I showed you a regular expression matcher + −
which works provably correctly in all cases.+ −
+ − \begin{center}+ −
\bl{$matcher\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$}+ −
\end{center}\bigskip\bigskip + −
+ − \small+ −
\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}+ −
+ − + −
\end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}+ −
+ − \begin{center}+ −
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}+ −
\bl{$der\, c\, (\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\+ −
\bl{$der\, c\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\+ −
\bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\+ −
\bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\+ −
\bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\+ −
& & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ + −
& & \bl{else $(der\, c\, r_1) \cdot r_2$}\\+ −
\bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause+ −
+ − \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\+ −
\bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\+ −
\end{tabular}+ −
\end{center}+ −
+ − + − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
+ − + − To see what is going on, define+ −
+ − \begin{center}+ −
\bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } + −
\end{center}\bigskip\bigskip+ −
+ − \small+ −
For \bl{$A = \{"f\!oo", "bar", "f\!rak"\}$} then+ −
+ − \begin{center}+ −
\bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}+ −
$Der\,f\,A$ & $=$ & $\{"oo", "rak"\}$\\+ −
$Der\,b\,A$ & $=$ & $\{"ar"\}$\\ + −
$Der\,a\,A$ & $=$ & $\varnothing$\\+ −
\end{tabular}}+ −
\end{center}+ −
+ −
+ − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − + − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}}+ −
+ − If we want to recognise the string \bl{$"abc"$} with regular expression \bl{$r$}+ −
then\medskip+ −
+ − \begin{enumerate}+ −
\item \bl{$Der\,a\,(L(r))$}\pause+ −
\item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause+ −
\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\pause+ −
\item finally we test whether the empty string is in this set\pause\medskip+ −
\end{enumerate}+ −
+ − The matching algorithm works similarly, just over regular expression instead of sets.+ −
\end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − + − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
+ − Input: string \bl{$"abc"$} and regular expression \bl{$r$} + −
+ − \begin{enumerate}+ −
\item \bl{$der\,a\,r$}+ −
\item \bl{$der\,b\,(der\,a\,r)$}+ −
\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause+ −
\item finally check whether the last regular expression can match the empty string+ −
\end{enumerate}+ −
+ − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
+ − We proved already+ −
+ − \begin{center}+ −
\bl{$nullable(r)$} \;if and only if\; \bl{$"" \in L(r)$}+ −
\end{center}+ −
+ − by induction on the regular expression.\bigskip\pause+ −
+ − \begin{center}+ −
\huge\bf \alert{Any Questions?}+ −
\end{center}+ −
+ − + − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
+ − We need to prove+ −
+ − \begin{center}+ −
\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}+ −
\end{center}+ −
+ − by induction on the regular expression.+ −
\end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − + − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}}+ −
+ − \begin{itemize}+ −
\item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip+ −
\item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already+ −
holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip+ −
\item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already+ −
holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip+ −
\item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already+ −
holds for \bl{$r$}.+ −
\end{itemize}+ −
+ − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}+ −
+ − \begin{itemize}+ −
\item \bl{$P$} holds for \bl{$0$} and+ −
\item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already+ −
holds for \bl{$n$}+ −
\end{itemize}\bigskip+ −
+ − \begin{itemize}+ −
\item \bl{$P$} holds for \bl{$""$} and+ −
\item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already+ −
holds for \bl{$s$}+ −
\end{itemize}+ −
+ − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − + − + − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}Languages\end{tabular}}+ −
+ − A \alert{language} is a set of strings.\bigskip+ −
+ − A \alert{regular expression} specifies a language.\bigskip+ −
+ − A language is \alert{regular} iff there exists+ −
a regular expression that recognises all its strings.\bigskip\bigskip\pause+ −
+ − \textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$}.}+ −
\end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[t]+ −
\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}+ −
+ − \begin{center}+ −
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}+ −
\bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\+ −
& \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / $[]$\\+ −
& \bl{$\mid$} & \bl{$c$} & character\\+ −
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\+ −
& \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\+ −
& \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\+ −
\end{tabular}+ −
\end{center}+ −
+ −
How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the+ −
set of languages we can recognise?+ −
+ −
\end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}}+ −
+ − \begin{itemize}+ −
\item \bl{$\sim{}r$} \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip+ −
\item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip+ −
\item \bl{$nullable (r) \dn not (nullable(r))$}\medskip+ −
\item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$}+ −
\end{itemize}\bigskip\pause+ −
+ − Used often for comments:+ −
+ − \[+ −
\bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /}+ −
\]+ −
+ − + − \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}Regular Exp's for Lexing\end{tabular}}+ −
+ − Lexing separates strings into ``words'' / components.+ −
+ − \begin{itemize}+ −
\item Identifiers (non-empty strings of letters or digits, starting with a letter)+ −
\item Numbers (non-empty sequences of digits omitting leading zeros)+ −
\item Keywords (else, if, while, \ldots)+ −
\item White space (a non-empty sequence of blanks, newlines and tabs)+ −
\item Comments+ −
\end{itemize}+ −
+ − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}Automata\end{tabular}}+ −
+ − A deterministic finite automaton consists of:+ −
+ − \begin{itemize}+ −
\item a 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 as argument and a character and produces a new state\smallskip\\+ −
this function might not always be defined+ −
\end{itemize}+ −
+ − \end{frame}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+ −
\mode<presentation>{+ −
\begin{frame}[c]+ −
\frametitle{\begin{tabular}{c}Automata\end{tabular}}+ −
+ − A deterministic finite automaton consists of:+ −
+ − \begin{itemize}+ −
\item a 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 as argument and a character and produces a new state\smallskip\\+ −
this function might not always be defined+ −
\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}}+ −
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + −
+ − + − \end{document}+ −
+ − %%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −
+ −