\documentclass[12pt, a4paper]{report}
 
\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2002 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Terceira Prova} \hfill 13/02/03

\begin{enumerate}
 \item Construa um aut\^omato com pillha determin\'{\i}stico que reconhe\c ca a
       linguagem $\{\verb+0+^m\verb+1+^n \,\,|\,\, m<n\}$.

 \item Construa um aut\^omato com pillha que reconhe\c ca, e uma gram\'atica
       livre do contexto que gere, as express\~oes aritm\'eticas
       na forma posfixada, EAPos, definidas recursivamente assim:
       \begin{enumerate}
        \item[(a)] \verb+n+ \'e uma EAPos;
        \item[(b)] se $x$ e $y$ s\~ao EAPos's, ent\~ao $xy\verb|+|$ e
                   $xy\verb|*|$ s\~ao EAPos's.
       \end{enumerate}

 \item Mostre que \'e ou n\~ao \'e linguagem livre do contexto:
       \begin{enumerate}
        \item $\{\verb+a+^{k}\,\,|\,\, k=n^2\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, \mbox{ o n\'umero de a's
              em $w$ \'e diferente do de b's}\}$.
       \end{enumerate}

 \item Obtenha uma gram\'atica sem regras $\lambda$ e sem regras unit\'arias
       equivalente \`a gram\'atica $(\{P,A,B,C,D\},\{\verb+a+,\verb+b+,
       \verb+d+\},R,P)$, onde $R$ consta da regras:

      \begin{enumerate}
       \item[\ \ ] $P\,\,\rightarrow\,\, AB\verb+a+C$
       \item[\ \ ] $A\,\,\rightarrow\,\, AB\,\,|\,\,BC$
       \item[\ \ ] $B\,\,\rightarrow\,\, \verb+b+\,\,|\,\,\lambda$
       \item[\ \ ] $C\,\,\rightarrow\,\, D\,\,|\,\,\lambda$
       \item[\ \ ] $D\,\,\rightarrow\,\, \verb+d+$
      \end{enumerate}

 \item Mostre que a gram\'atica da quest\~ao anterior \'e amb\'{\i}gua.
\end{enumerate}

\end{document}
 
