\documentclass{beamer}
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[all]{xy}

\usetheme{Berkeley}

\begin{document}

\title{Autômato Finito}
\author{Carlos Campani}

\pgfdeclareimage[height=1.5cm]{logo}{ufpellogo}
\logo{\pgfuseimage{logo}}

\frame{\titlepage}

\frame{
\frametitle{Sumário}
\tableofcontents
}

\AtBeginSection[]
{
 \begin{frame}
  \frametitle{Sumário}
  \tableofcontents[currentsection]
 \end{frame}
}
\section{Introdução}
\begin{frame}
\frametitle{O que é o autômato finito?}
\begin{itemize}
\item <1-> Modelo formal de sistema;
\item <2-> Sistema de estados finitos;
 \begin{itemize}
 \item <3-> Modelo matemático com entradas e saídas discretas;
 \item <4-> Pode assumir um número finito de estados.
 \end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Para que serve?}
\begin{itemize}
\item <1-> Reconhecedor das linguagens regulares;
\item <2-> Modelo computacional simples;
\item <3-> Analisador léxico de compiladores.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Quais as partes de um autômato finito?}
\begin{block}{Fita de Entrada}<1->
Dispositivo de entrada que contém a informação a ser processada.
\end{block}

\begin{block}{Unidade de Controle}<2->
Reflete o estado da máquina. Possui uma unidade de leitura (cabeçote da fita) que acessa a fita de entrada.
\end{block}

\begin{block}{Programa ou Função de Transição}<3->
Função que controla a leitura da fita e as transições de estados.
\end{block}
\end{frame}

\section{Definição de Autômato Finito}
\setbeamercovered{transparent}
\begin{frame}
\frametitle{Definição Formal}
\begin{block}{Definição}
Um \emph{autômato finito} $M$ sobre um alfabeto $\Sigma$ é um sistema $(K,\Sigma,\delta,q_0,F)$ onde:

\uncover<1->{$\mathbf{K}$ -- conjunto finito, não vazio, de estados;}

\uncover<1,3->{$\mathbf{\Sigma}$ -- alfabeto finito de entrada;}

\uncover<1,4->{$\mathbf{\delta}$ -- função de transição de estados, $\delta:K\times \Sigma\bigcup\{\varepsilon\}\rightarrow K$;}

\uncover<1,5->{$\mathbf{q_0\in K}$ -- estado inicial;}

\uncover<1,6->{$\mathbf{F\subset K}$ -- conjunto de estados finais.}

\end{block}
\end{frame}
\setbeamercovered{invisible}

\section{Representação dos Autômatos}
\begin{frame}{Diagrama de Transição}
\begin{itemize}
\item <1-> Permite representar graficamente os autômatos;
\item <2-> Simplifica a representação e facilita a visualização.
\end{itemize}
\end{frame}

\begin{frame}{Diagrama de Transição}
\xymatrix@C=2pt{
& *++[o][F-]{q_1}\ar[rr]^a\ar@{.>}[dl] & \ar@{.>}[d] & *++[o][F-]{q_2}\ar@{.>}[dr] \\
\txt{estado anterior} & & \txt{transição} & & \txt{estado após transição}
}
\begin{enumerate}
\item <2-> O autômato está inicialmente no estado $q_1$;
\item <3-> ``a'' está na fita de entrada;
\item <4-> O autômato muda de estado para o estado $q_2$.
\end{enumerate}
\end{frame}

\begin{frame}{Exemplo de Reconhecimento}

\begin{columns}[t]

\begin{column}{5cm}
\pgfdeclareimage[width=5cm]{automato1}{automato1}
\pgfuseimage{automato1}<1>
\pgfdeclareimage[width=5cm]{automato2}{automato2}
\pgfuseimage{automato2}<2>
\pgfdeclareimage[width=5cm]{automato3}{automato3}
\pgfuseimage{automato3}<3>
\pgfdeclareimage[width=5cm]{automato4}{automato4}
\pgfuseimage{automato4}<4>
\end{column}

\begin{column}{5cm}
\begin{itemize}
\item <1- | alert@1> Reconhecimento inicia no estado $q_1$
\item <2- | alert@2> Transição para estado $q_2$
\item <3- | alert@3> Lê $0$ e fica no estado $q_2$
\item <4- | alert@4> Transição para o estado final $q_3$
\end{itemize}

\[\xymatrix{
*++[o][F-]{q_1} \ar@(ul,ul)[] \ar[r]^{1}
\ar[d]^{0} & *++[o][F=]{q_3} \\
*++[o][F-]{q_2} \ar[ur]_{1} \ar@(dl,d)[]_{0} }\]

\end{column}

\end{columns}

\end{frame}

\begin{frame}{Exemplo de Reconhecimento}
\transdissolve

\begin{columns}[t]

\begin{column}{5cm}
\pgfdeclareimage[width=5cm]{automato5}{automato5}
\pgfuseimage{automato5}
\end{column}

\begin{column}{5cm}
\begin{itemize}
\item Reconhecimento inicia no estado $q_1$
\item Transição para estado $q_2$
\item Lê $0$ e fica no estado $q_2$
\item Transição para o estado final $q_3$
\end{itemize}

\[\xymatrix{
*++[o][F-]{q_1} \ar@(ul,ul)[] \ar[r]^{1}
\ar[d]^{0} & *++[o][F=]{q_3} \\
*++[o][F-]{q_2} \ar[ur]_{1} \ar@(dl,d)[]_{0} }\]

\end{column}

\end{columns}

\end{frame}

\section{Relação entre Gramática Regular e Autômato Finito}
\begin{frame}{AF $\leftrightarrow$ GR}
\transsplitverticalout[duration=2]
\begin{block}{GR $\rightarrow$ AF}
Se $L$ é uma linguagem regular então existe um AF que reconhece $L$.
\end{block}

\begin{block}{AF $\rightarrow$ GR}
Se $L$ é reconhecida por um AF então existe uma GR que gera $L$.
\end{block}
\end{frame}

\section{Conclusão}
\begin{frame}{Conclusão}
\begin{itemize}
\item<1-> Autômato finito é um modelo matemático importante em ciência da
  computação;
\item<2-> Aplica-se no projeto de analisador léxico em compiladores.
\end{itemize}
\end{frame}

\begin{frame}{Para saber mais}
\nocite{bib:blauth}
\bibliography{campani}
\bibliographystyle{plain}
\end{frame}

\end{document}