\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}