\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{verbatim}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}


\newcounter{conta}
\newcounter{conta2}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova} \hfill 21/09/2009

\vspace*{3mm}
\begin{flushleft}
 A segunda quest\~ao vale 6 pontos. As outras valem 5 pontos cada uma.
\end{flushleft}
\vspace*{1mm}
\begin{enumerate}
 \item Seja o alfabeto $\Sigma=\{{\tt 0},{\tt 1}\}$ e as linguagens
       $A=\Sigma^*\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\Sigma^*$ e $B=\Sigma\{{\tt 0}\}\Sigma^*$. Usando uma
       express\~ao obtida a partir de \textit{conjuntos finitos} e opera\c{c}\~oes dentre \textit{uni\~ao},
       \textit{concatena\c{c}\~ao} e \textit{fecho de Kleene}, expresse:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\overline{A}$.
        \item $\overline{B}$.
        \item $B-A$.
       \end{list}
 \item Seja a linguagem $L$ assim definida, recursivamente:
       \begin{itemize}
        \item $\lambda,{\tt 0},{\tt 1}\in L$;
        \item se $x\in L$ ent\~ao ${\tt 0}x{\tt 0},{\tt 1}x{\tt 1}\in L$.
       \end{itemize}
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Fa\c{c}a uma gram\'atica que gere $L$.
        \item Fa\c{c}a uma gram\'atica que gere $\overline{L}$.
        \item Prove que $L$ \'e ou que n\~ao \'e regular.
       \end{list}
 \item Encontre um AFD que reconhe\c{c}a $\{{00},{1}\}^*\{{0},{11}\}^*$.
 \item Partindo do AFN$\lambda$ a seguir, obtenha um AFD equivalente. Dever\'a ficar claro o
       m\'etodo utilizado para elimina\c{c}\~ao das transi\c{c}\~oes $\lambda$.

        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,25)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

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

          \drawedge[curvedepth=0](A,B){$\lambda$}
          \drawedge[curvedepth=3](A,C){{\tt 0}}
          \drawedge[curvedepth=3](B,D){{\tt 1}}
          \drawedge[curvedepth=3](C,A){{\tt 1}}
          \drawedge[curvedepth=0](C,D){$\lambda$}
          \drawedge[curvedepth=3](D,B){{\tt 0}}
         \end{picture}
        }
 \item Sejam $L_1=\{{0}^n \,|\, n \mbox{ \'e um n\'umero primo}\}$ e $L_2=\{{\tt 0}\}^k\{{\tt 0}\}^*$, onde
       $k$ \'e uma constante. Para cada linguagem a seguir, mostre que ela \'e regular ou que n\~ao \'e:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $L_1-L_2$.
        \item $L_1\cap L_2$.
        \item $L_1\cup L_2$.
       \end{list}
\end{enumerate}

\end{document}
