summaryrefslogtreecommitdiff
path: root/info/portuguese/beamer/src/exemplo/exemplo.tex
diff options
context:
space:
mode:
Diffstat (limited to 'info/portuguese/beamer/src/exemplo/exemplo.tex')
-rw-r--r--info/portuguese/beamer/src/exemplo/exemplo.tex199
1 files changed, 199 insertions, 0 deletions
diff --git a/info/portuguese/beamer/src/exemplo/exemplo.tex b/info/portuguese/beamer/src/exemplo/exemplo.tex
new file mode 100644
index 0000000000..18c502efde
--- /dev/null
+++ b/info/portuguese/beamer/src/exemplo/exemplo.tex
@@ -0,0 +1,199 @@
+\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}
+