\documentclass[11pt,a4paper]{book}

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

\newcounter{conta}
\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 Segunda Prova} \hfill 04/11/2009

\vspace*{3mm}
\begin{flushleft}
Cada item vale 3 pontos.
\end{flushleft}

\begin{enumerate}
 \item Seja $M$ o aut\^omato finito com o seguinte diagrama de estados:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,20)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(20,8){1}
          \node[Nmarks=r](2)(40,12){2}
          \node[Nmarks=r](3)(60,8){3}

          \drawloop[loopangle=90](1){{\tt b}}
          \drawedge[curvedepth=0](1,2){{\tt a}}
          \drawloop[loopangle=90](2){{\tt a}}
          \drawedge[curvedepth=2](2,3){{\tt b}}
          \drawedge[curvedepth=2](3,2){{\tt a}}
          \drawedge[curvedepth=7](3,1){{\tt b}}
         \end{picture}
        }
      \end{center}
      Usando m\'etodos vistos em aula ou do livro-texto: 
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item obtenha uma gram\'atica regular que gere $L(M)$;
       \item obtenha uma express\~ao regular que denote $L(M)$.
      \end{list} 
 
 \item Para cada linguagem a seguir, construa um APD, se poss\'{\i}vel. Se n\~ao for poss\'{\i}vel,
       construa um APN. Crit\'erio de reconhecimento: por estado final {\bf e} pilha vazia.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^n{\tt 1}^k\,|\, n>k\}$.
        \item $\{{\tt 0}^n{\tt 1}^k\,|\, n<k\}$.
       \end{list}

 \item Seja $L=\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m\geq n \mbox{ ou } n\geq k\}$.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Fa\c{c}a uma GLC $G$ que gere $L$.
        \item Mostre que $G$ \'e amb\'{\i}gua.
       \end{list}

 \item Seja a GLC $G=(\{P,A,B,Q,R\},\{{\tt a},{\tt b}\},X,P)$ em que $X$ cont\'em as regras:
              \begin{quote}
               $P\,\rightarrow\, Q \,|\, R$ \\
               $Q \,\rightarrow\, {\tt a}Q{\tt a} \,|\, B$ \\
               $B \,\rightarrow\, {\tt b}B{\tt b} \,|\, \lambda$ \\
               $R \,\rightarrow\, {\tt b}R{\tt b} \,|\, A$ \\
               $A \,\rightarrow\, {\tt a}A{\tt a} \,|\, \lambda$
              \end{quote} 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Usando m\'etodos vistos em aula ou do livro-texto, construa uma GLC $G'$, equivalente a $G$,
              sem regras $\lambda$ e sem regras unit\'arias.
        \item Construa uma GLC equivalente a $G'$ na forma normal de Greibach.
       \end{list}

 \item Prove que $\{{\tt a}^i{\tt b}^j{\tt c}^n\,|\, i<n \mbox{ e } j<n\}$ n\~ao \'e LLC.
\end{enumerate}

\end{document}
