\documentclass[11pt,a4paper]{report}

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

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

\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
 
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2014 \\
Professor: Newton José Vieira \\
 
\noindent {\bf Segunda Prova} \hfill 28/10/2014

\vspace*{3mm}
\noindent As questões 1, 2 e 3 valem 5 pontos e as duas últimas valem 4 pontos cada uma.

\vspace*{3mm}
\begin{enumerate}
 \item Construa um AFD que reconheça a linguagem denotada por $(01)^*(00+1)^*01$.

 \item Obtenha uma expressão que denote a linguagem reconhecida pelo AFD:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,38)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(20,28){1}
          \node[Nmarks=r](2)(50,28){2}
          \node(3)(50,8){3}
          \node[Nmarks=r](4)(20,8){4}

          \drawloop[loopangle=90](1){{\tt 1}}
          \drawedge[curvedepth=0](1,2){{\tt 0}}
          \drawloop[loopangle=90](2){{\tt 0}}
          \drawedge[curvedepth=0](2,3){{\tt 1}}
          \drawloop[loopangle=270](3){{\tt 1}}
          \drawedge[curvedepth=0](3,4){{\tt 0}}
          \drawedge[curvedepth=0](4,1){{\tt 1}}
          \drawedge[curvedepth=0](4,2){{\tt 0}}
         \end{picture}
        }
      \end{center}
     
 \item Construa uma GLC que gere $\{\verb+a+^m\verb+b+^n\verb+c+^k \,|\, m\geq n \mbox{ ou } n\leq k\}$. Prove que sua
       GLC é ambígua mostrando duas derivações mais a esquerda de $\lambda$ (se houver).

 \item Seja a GLC:
     	\begin{enumerate}
	     \item[\ ] $P\,\rightarrow\, A \,|\, {\tt 10}$
     	 \item[\ ] $A\,\rightarrow\, {\tt 0} A {\tt 1} \,|\, B$
	     \item[\ ] $B\,\rightarrow\, {\tt 00}B \,|\, B{\tt 11} \,|\, \lambda$
	    \end{enumerate}
 	    Aplique, em sequência, os métodos vistos em aula para:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item eliminar regras $\lambda$;
       \item eliminar regras unitárias.
       \item obter uma GLC equivalente na forma normal de Chomsky.
      \end{list}

 \item Prove que $\{\verb+a+^m\verb+b+^n\verb+c+^k \,|\, k=\textit{min}(m,n)\}$ é ou que não é livre do contexto.
       $\textit{min}(m,n)$ é o menor valor entre $m$ e $n$.
\end{enumerate}

\end{document}

