diff options
author | Karl Berry <karl@freefriends.org> | 2009-05-19 18:31:20 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2009-05-19 18:31:20 +0000 |
commit | 43e88513fde379d0b288917e4e2e7bb876ae9c18 (patch) | |
tree | c5b98c72450e5fb70603263a73049bc4e9e1805a /Master/texmf-dist/doc/latex/beamer-tut-pt/exemplo.tex | |
parent | 56a93add8636acfb8938079ed457a5a0308c1523 (diff) |
move beamer-tut-pt out of texmf-doc
git-svn-id: svn://tug.org/texlive/trunk@13242 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/doc/latex/beamer-tut-pt/exemplo.tex')
-rw-r--r-- | Master/texmf-dist/doc/latex/beamer-tut-pt/exemplo.tex | 199 |
1 files changed, 199 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/beamer-tut-pt/exemplo.tex b/Master/texmf-dist/doc/latex/beamer-tut-pt/exemplo.tex new file mode 100644 index 00000000000..18c502efde4 --- /dev/null +++ b/Master/texmf-dist/doc/latex/beamer-tut-pt/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} + |