\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Solução do professor -- Turma D\hfill {11/10/2012}

\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Sejam $\Sigma=\{{\tt a},{\tt b}\}$,  $A=\{{\tt a}\}\Sigma^+$ e $B=\Sigma^*\{{\tt b}\}$.
       Descreva uma condição necessária e suficiente para que uma palavra de $\Sigma^*$ pertença a:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $AA$
        \item $A\cap B$
        \item $A-B$
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Começa com {\tt a}, tem no mínimo 4 símbolos e tem algum {\tt a} do terceiro ao penúltimo símbolos.
        \item Começa com {\tt a} e termina com {\tt b}.
        \item Começa com {\tt a}, tem no mínimo dois símbolos e termina com {\tt a}.
       \end{list}

 \item {\footnotesize Seja a gramática $G=(\{P,A\},\{{\tt a},{\tt b}\},R,P)$.
       \begin{enumerate}
        \item[$R$:] $P\,\rightarrow\,{\tt a}P{\tt a}\,|\, A$
        \item[\ ]   $A\,\rightarrow\,{\tt b}A{\tt b} \,|\, \lambda$
       \end{enumerate}
       Descreva $L(G)$.}

       \textit{Solução}: $L(G)=\{{\tt a}^n{\tt b}^{2k}{\tt a}^n\,|\,n,k\geq 0\}$.


 \item {\footnotesize Construa uma gramática que gere $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt ab}
       nem {\tt bc}}\}$.}

       \textit{Solução}:
       \begin{quote}
        $X\,\rightarrow\,{\tt a}A \,|\, {\tt b}B \,|\, {\tt c}X \,|\, \lambda$ \\
        $A\,\rightarrow\,{\tt a}A \,|\, {\tt c}X \,|\, \lambda$ \\
        $B\,\rightarrow\,{\tt a}A \,|\, {\tt b}B \,|\, \lambda$
       \end{quote}

 \item {\footnotesize Construa um AFD que reconheça $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt ab}
       nem {\tt bc}}\}$.}

       \textit{Solução}:

       \begin{picture}(120,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](X)(20,10){X}
        \node[Nmarks=r](A)(40,10){A}
        \node[Nmarks=r](B)(60,10){B}

        \drawloop[loopangle=90](X){{\tt c}}
        \drawedge[curvedepth=3](X,A){{\tt a}}
        \drawedge[curvedepth=-10](X,B){{\tt b}}
        \drawloop[loopangle=90](A){{\tt a}}
        \drawedge[curvedepth=3](A,X){{\tt c}}
        \drawloop[loopangle=90](B){{\tt b}}
        \drawedge[curvedepth=0](B,A){{\tt a}}
       \end{picture}

 \item {\footnotesize Responda às perguntinhas, justificando:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\lambda$ pode ser símbolo de um alfabeto?
        \item Todo AFD tem estado de erro (a partir do qual não se alcança estado final). Certo ou errado?
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Não, pois se $\Sigma$ é um alfabeto, $\lambda$ é uma \underline{palavra} em $\Sigma^*$.
        \item Errado, pois se toda palavra do alfabeto é prefixo de alguma que pertença à linguagem reconhecida,
              então o AFD não tem estado de erro.
       \end{list}

\end{enumerate}

\end{document}
