\documentclass[12pt,a4paper]{report}

\usepackage{amsfonts}
\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}

\usepackage{gastex}
\usepackage[usenames]{color}
\pagestyle{empty}
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
 
\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2016 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova} \hfill 07/04/2016

\vspace*{3mm}
\begin{enumerate}
 \item Sejam $A=\{\lambda,{\tt 0}\}$, $B=\{{\tt 0},{\tt 11}\}$ e $C=\{{\tt 00},{\tt 1}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Calcule $AAB$.
				\item Quantas palavras há na linguagem $A^k$, sendo $k\in\mathbb{N}$?
				\item Dê, em português, uma condição necessária e suficiente para que uma palavra pertença a
				      $\{{\tt 00}\}^*\cap B^*$.
        \item Descreva $B^*\cap C^*$.
       \end{list}

  \item Obtenha gramáticas para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}^*\{{\tt 1}\}^+$;
        \item $\{xyx^R\,|\, x\in\{{\tt a},{\tt b}\}^* \mbox{ e } y\in\{{\tt c}\}^*\}$.
       \end{list}

 \item Construa AFDs que reconheçam as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 11}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o último símbolo de $w$ é idêntico ao primeiro}\}$.
       \end{list}

 \item Sejam $B=\{{\tt 0},{\tt 11}\}$ e $C=\{{\tt 00},{\tt 1}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFD que reconheça $\overline{C^*}$. \textit{Dica}: faça antes um AFD para $C^*$.
        \item Construa um AFD que reconheça $B^*-C^*$. \textit{Dica}: utilize produto de autômatos.
       \end{list}

 \item Sobre AFNs:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa o diagrama de estados de um AFN que reconheça:
				      $$\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ contém apenas um {\tt a} ou apenas um
							{\tt b} ou apenas um {\tt c}}\}\mbox{.}$$
        \item Usando o método visto no curso, construa um AFD equivalente ao AFN:

              \begin{picture}(120,15)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, filllgray=0.9, loopdiam=4}

               \node[Nmarks=i, iangle=180](1)(15,5){1}
               \node[Nmarks=ir, iangle=90](3)(35,5){3}
               \node[Nmarks=i, iangle=0](2)(55,5){2}

               \drawedge[curvedepth=0](1,3){\tt a}
               \drawedge[curvedepth=3](2,3){\tt b}
               \drawedge[curvedepth=3](3,2){\tt a}

              \end{picture}
      \end{list}

\item Construa um AFN equivalente ao AFN$\lambda$ a seguir usando o método visto  em aula.

      \begin{picture}(120,15)\setlength{\unitlength}{1mm}
       \gasset{Nw=6, Nh=6, Nmr=3, filllgray=0.9, loopdiam=4}

       \node[Nmarks=r](B)(20,5){B}
       \node[Nmarks=i, iangle=270](A)(40,5){A}
       \node[Nmarks=r](C)(60,5){C}

       \drawloop[loopangle=90](B){\tt b}
       \drawedge[curvedepth=0,ELside=r](A,B){$\lambda$}
       \drawloop[loopangle=90](A){\tt a}
       \drawedge[curvedepth=0](A,C){$\lambda$}
       \drawloop[loopangle=90](C){\tt c}
      \end{picture}
\end{enumerate}

\vspace*{2mm}
\noindent \textbf{Abreviaturas:}
\begin{quote}
 AFD: autômato finito determinístico. \\
 AFN: autômato finito não determinístico. \\
 AFN$\lambda$: autômato finito não determinístico com transições $\lambda$.
\end{quote}
\end{document}
