\documentclass[11pt,a4paper]{article}

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

\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

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

\begin{document}
 
\vspace*{13mm}
\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 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova} \hfill 09/09/2010

\vspace*{2mm}
\begin{flushleft}
 Os itens de cada questão têm o mesmo peso.
\end{flushleft}
%\vspace*{1mm}
\begin{enumerate}
 \item Sejam as linguagens $L_1=\{{\tt 1}\}^*\{\lambda,{\tt 0}\}\{{\tt 1}\}^*$ e $L_2=\{{\tt 01},{\tt 1}\}^*$.
       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{L_1}$.
        \item $L_1\cap L_2$.
        \item $L_2-L_1$.
%        \item $\overline{B}$.
       \end{list}
 \item Seja a gramática $G=(\{A,B\},\{{\tt 0},{\tt 1}\},R,A)$ em que $R$ tem apenas as regras:
       \begin{enumerate}
        \item[\ ] $A\,\rightarrow\, {\tt 0}A{\tt 1} \,|\, B$
        \item[\ ] $B\,\rightarrow\, {\tt 1}B{\tt 0} \,|\, \lambda$
       \end{enumerate}
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item O que é $L(G)$?
        \item Fa\c{c}a uma gram\'atica que gere $\overline{L(G)}$.
        \item Prove que $L(G)$ n\~ao \'e regular.
       \end{list}
 \item Encontre AFDs que reconhe\c{c}am as linguagens:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01},{\tt 1}\}^*$.
        \item O complemento da linguagem anterior.
        \item $\{{\tt 01},{\tt 1}\}^*\cap\{{\tt 00},{\tt 01},{\tt 10},{\tt 11}\}^*$.
       \end{list}
 \item Seja o seguinte AFN$\lambda$:

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

          \node[Nmarks=i](1)(20,20){1}
          \node[Nmarks=r](3)(40,20){3}
          \node[Nmarks=i](2)(20,5){2}
          \node[Nmarks=r](4)(40,5){4}

          \drawloop(1){${\tt a}$}
          \drawedge[curvedepth=0](1,3){$\lambda$}
          \drawloop(2){${\tt c}$}
          \drawedge[curvedepth=0](2,3){{\tt c}}
          \drawedge[curvedepth=0](2,4){$\lambda$}
          \drawloop(3){${\tt b}$}
          \drawloop(4){${\tt a}$}
         \end{picture}
        }
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Obtenha um AFN equivalente pela eliminação das transições $\lambda$. Dever\'a ficar claro
              o \underline{m\'etodo} utilizado para elimina\c{c}\~ao das transi\c{c}\~oes $\lambda$
        \item Obtenha um AFD equivalente ao AFN. Dever\'a ficar claro o \underline{m\'etodo} utilizado. 
       \end{list}

 \item Mostre que:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item se $L$ não é uma linguagem regular, então $\overline{L}$ também não é.
        \item Se $L_1$ e $L_2$ são linguagens regulares, então $\{w\in L_1\cup L_2 \,|\, w\not\in L_1 \mbox{ ou }
              w\not\in L_2\}$ também é.
        \item Para todo AFN existe AFN equivalente com um único estado final.
       \end{list}
\end{enumerate}

\end{document}
