\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\newcounter{conta2}
\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 W\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 $AB$
        \item $BB$
        \item $B-A$
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Começa com {\tt a}, termina com {\tt b} e tem no mínimo três símbolos.
        \item Termina com {\tt b} e tem no mínimo mais um {\tt b}.
        \item Começa e termina com {\tt b}.
       \end{list}

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

       \textit{Solução}: $L(G)=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,|w| \mbox{ é ímpar}\}$.

 \item {\footnotesize Construa uma gramática que gere $\{\lambda,{\tt 0}\}\{{\tt 11}\}^*\{\lambda,{\tt 0}\}$.}

       \textit{Solução}:
       \begin{quote}
        $X\,\rightarrow\,ABA$ \\
        $A\,\rightarrow\,{\tt 0} \,|\, \lambda$ \\
        $B\,\rightarrow\,{\tt 11}B \,|\, \lambda$
       \end{quote}

 \item {\footnotesize Construa um AFD que reconheça $\{\lambda,{\tt 0}\}\{{\tt 11}\}^*\{\lambda,{\tt 0}\}$.}

       \textit{Solução}:

       \begin{picture}(120,25)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](1)(20,20){}
        \node[Nmarks=r](2)(40,20){}
        \node(3)(30,5){}
        \node[Nmarks=r](5)(60,20){}

        \drawedge[curvedepth=0](1,2){{\tt 0}}
        \drawedge[curvedepth=0, ELside=r](1,3){{\tt 1}}
        \drawedge[curvedepth=3](2,3){{\tt 1}}
        \drawedge[curvedepth=0](2,5){{\tt 0}}
        \drawedge[curvedepth=3](3,2){{\tt 1}}
       \end{picture}


 \item {\footnotesize Responda às perguntinhas, justificando:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $\Sigma$ é um alfabeto, o conjunto potência de $\Sigma^*$ \'e:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item o conjunto de todas as palavras no alfabeto $\Sigma$; ou
               \item o conjunto de todas as linguagens de alfabeto $\Sigma$; ou
               \item não é conjunto?
              \end{list}
        \item Se uma variável aparece em uma única regra de uma gramática ela é inútil. Certo ou errado?
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto potência de $\Sigma^*$ é o conjunto de todos os subconjuntos de $\Sigma^*$. Como cada
              subconjunto de $\Sigma^*$ é uma linguagem de alfabeto $\Sigma$, o conjunto potência de $\Sigma^*$ é
              o conjunto de todas as linguagens de alfabeto $\Sigma$.
        \item Certo, a menos que ela seja a variável de partida. Se a variável ocorrer do lado esquerdo de uma
              regra, mas não do lado direito, não haverá como aplicar a regra. Se a variável ocorrer apenas do
              lado direito de uma regra, quando aparecer em uma forma sentencial, será impossível eliminá-la.
       \end{list}

\end{enumerate}

\end{document}
