\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{1}^{\mbox{\underline{o}}}$ semestre de 2001 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Terceira Prova} \hfill 12/06/01

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

 \item Construa um APD que reconhe\c ca 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}
       {\em Sugest\~ao\/}: use os seguintes fatos, facilmente demonstr\'aveis por indu\c c\~ao:
       \begin{itemize}
        \item qualquer palavra que tenha mais \verb+n+'s que operadores \'e prefixo de uma EAPos;
        \item o n\'umero de \verb+n+'s \'e um mais que o de operadores.
       \end{itemize}

 \item Construa um APN\footnote{Aut\^omato com pillha n\~ao determin\'{\i}stico.} que reconhe\c ca a
       linguagem $\{\verb+0+^m\verb+1+^n \,\,|\,\, m>n\}$:
       \begin{enumerate}
        \item por estado final;
        \item por pilha vazia.
       \end{enumerate}

 \item Construa gram\'aticas livres do contexto para as linguagens:
       \begin{enumerate}
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^{2(m+n)}\,\,|\,\, m,n\geq 0\}$
        \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}
 
