\documentclass[11pt,a4paper]{book}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\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 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova} \hfill 24/09/2007

\begin{enumerate}
 \item Seja a gram\'atica $G=(\{A,B\},\{{\tt a},{\tt b}\},R,A)$ em que $R$ \'e
       cons\-ti\-tu\'{\i}\-do das quatro regras:
       \begin{enumerate}
        \item[\ \ \ ] $A\rightarrow {\tt a} A {\tt b}\,|\, B$
        \item[\ \ \ ] $B\rightarrow {\tt b} B \,|\, \lambda$
      \end{enumerate}
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Apresente um esquema de deriva\c{c}\~ao que mostre como derivar
             qualquer palavra de $L(G)$.
       \item Descreva $L(G)$.
       \item Prove que $L(G)$ \'e ou n\~ao \'e regular.
      \end{list} 
 
 \item Obtenha um AFD que reconhe\c{c}a $\{{\tt 00},{\tt 11}\}^*\{{\tt 01},{\tt 10}\}^*$.

 \item Seja o AFD com o seguinte diagrama de estados:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(100,40)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(10,20){1}
          \node(2)(30,30){2}
          \node(3)(30,10){3}
          \node[Nmarks=r](4)(50,30){4}
          \node(5)(50,10){5}
          \node[Nmarks=r](6)(70,30){6}
          \node(7)(70,10){7}
          \node(8)(90,20){8}

          \drawedge[curvedepth=2](1,2){{\tt 0}}
          \drawedge[curvedepth=0, ELside=r](1,3){{\tt 1}}
          \drawedge[curvedepth=2](2,1){{\tt 0}}
          \drawedge[curvedepth=0](2,3){{\tt 1}}
          \drawedge[curvedepth=0, ELside=r](3,4){{\tt 0}}
          \drawloop[loopangle=270](3){{\tt 1}}
          \drawedge[curvedepth=0](4,5){{\tt 0}}
          \drawedge[curvedepth=0](4,6){{\tt 1}}
          \drawloop[loopangle=270](5){{\tt 0}}
          \drawedge[curvedepth=2](5,7){{\tt 1}}
          \drawedge[curvedepth=0](6,7){{\tt 0}}
          \drawloop[loopangle=90](6){{\tt 1}}
          \drawedge[curvedepth=2](7,5){{\tt 0}}
          \drawloop[loopangle=270](7){{\tt 1}}
          \drawedge[curvedepth=0, ELside=r](8,6){{\tt 0}}
          \drawedge[curvedepth=0](8,7){{\tt 1}}
         \end{picture}
        }
       \end{center}
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Obtenha o diagrama de estados de um AFD m\'{\i}nimo equivalente.
             (Denote cada estado como um conjunto de estados equivalentes.)
       \item Que linguagem \'e reconhecida pelo AFD em quest\~ao?
      \end{list}     
      
 \item Seja o AFN com o seguinte diagrama de estados:
       \begin{center}
        \begin{picture}(60,15) \setlength{\unitlength}{1mm}
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=i, iangle=0](i1)(50,5){$i_1$}
         \node[Nmarks=i](i0)(10,5){$i_0$}
         \node[Nmarks=r](f)(30,5){$f$}
      
         \drawedge[curvedepth=0](i0,f){{\tt 0}}
         \drawloop[loopangle=90](i0){{\tt 1}}
         \drawedge[curvedepth=0, ELside=r](i1,f){{\tt 1}}
         \drawloop[loopangle=90](i1){{\tt 0}}
        \end{picture}
       \end{center}
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Que linguagem \'e reconhecida pelo AFN em quest\~ao?
       \item Obtenha um AFD equivalente pelo m\'etodo de constru\c{c}\~ao-de-subconjuntos.
      \end{list}     

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares, utilizando
       pro\-prie\-da\-des de fechamento:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 1000\}$;
        \item $\{{\tt 0}^m{\tt 1}^n\,|\, m\not=n\}$.
       \end{list}     
\end{enumerate}

\end{document}