\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\newcounter{conta2}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill $1^{\mbox{\underline{o}}}$ semestre de 2000 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf S\'etima Lista de Exerc\'{\i}cios} \hfill Data de entrega: 06/06/2000

\begin{enumerate}
 \item Construa APND's que reconhe\c cam as seguintes linguagens por estado final e pilha vazia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item $\{\verb+0+^n\verb+1+^n\,\,|\,\, n\geq 0\}\cup\{\verb+0+^n\verb+1+^{2n}\,\,|\,\, n\geq 0\}$
         \item $\{\verb+0+^n\verb+1+^k\,\,|\,\, n\leq k\leq 2n\}$
         \item $\{\verb+0+^n\verb+1+^k\,\,|\,\, n\not= k\}$
       \end{list}
 \item Construa APD's que reconhe\c cam $\{\verb+0+^n\verb+1+^n\,\,|\,\, n\geq 0\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item por estado final;
        \item por pilha vazia.
       \end{list}
 \item Construa APND's que reconhe\c cam $\{\verb+0+^n\verb+1+^k\,\,|\,\, n\not= k\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item por estado final;
        \item por pilha vazia.
       \end{list}
 \item Seja $L$ uma linguagem qualquer. Mostre que as seguintes afirmativas s\~ao equivalentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Existe um APND que aceita $L$ por estado final e pilha vazia.
        \item Existe um APND que aceita $L$ por estado final.
        \item Existe um APND que aceita $L\cup\{\lambda\}$ por pilha vazia.
       \end{list}
       (Mostre como tranformar um APND de um tipo em outro. Observe que bastam 3 (e n\~ao 4 ou 6)
       transforma\c c\~oes, se estas forem convenientemente escolhidas.)

 \item Construa gram\'aticas livres do contexto para as linguagens::
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\verb+a+^n\verb+b+^{2n}\verb+c+^k\,\,|\,\, n,k\geq 0\}$
          \item $\{\verb+a+^n\verb+b+^k\verb+c+^{2n+k}\,\,|\,\, n,k\geq 0\}$
          \item $\{\verb+a+^n\verb+b+^k\,\,|\,\, n\leq k\leq 2n\}$
          \item $\{\verb+a+^n\verb+b+^k\verb+c+^m\,\,|\,\, n\leq k\leq 2n+m\}$
         \end{list}
 \item Verifique quais dentre as gram\'aticas da quest\~ao anterior s\~ao amb\'{\i}guas. Para as que forem
       amb\'{\i}guas, determine as {\em menores\/} palavras para as quais existam \'arvores de deriva\c c\~ao
       diferentes.
 \item Elimine as regras $\lambda$ das seguintes gram\'aticas:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $G_1=(\{A,B,C\},\{\verb+0+,\verb+1+\},R,A)$, onde $R$ consta das regras:
                \begin{enumerate}
                 \item[\ \ \ ] $A\rightarrow \verb+0+ A \,\,|\,\, \verb+1+ A \,\,|\,\, B$
                 \item[\ \ \ ] $B\rightarrow \verb+00+ A \,\,|\,\, \verb+0+ C \,\,|\,\, \lambda$
                 \item[\ \ \ ] $C\rightarrow \verb+1+ C \,\,|\,\, \lambda$
                \end{enumerate}
          \item $G_2=(\{A,B,C,D\},\{\verb+0+,\verb+1+,\verb+2+\},R,A)$, onde $R$ consta das regras:
                \begin{enumerate}
                 \item[\ \ \ ] $A\rightarrow BCD \,\,|\,\, \verb+0+ CC \,\,|\,\, \verb+1+ DD$
                 \item[\ \ \ ] $B\rightarrow \verb+0+ B \,\,|\,\, \verb+0+ CD$
                 \item[\ \ \ ] $C\rightarrow \verb+1+ C \,\,|\,\, \lambda$
                 \item[\ \ \ ] $D\rightarrow \verb+2+ D \verb+2+ \,\,|\,\, \lambda$
                \end{enumerate}
        \end{list}
 \item Elimine as regras unit\'arias das seguintes gram\'aticas:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $G_1=(\{A,B,C\},\{\verb+0+,\verb+1+\},R,A)$, onde $R$ consta das regras:
                \begin{enumerate}
                 \item[\ \ \ ] $A\rightarrow \verb+0+ A \,\,|\,\, \verb+1+ A \,\,|\,\, B$
                 \item[\ \ \ ] $B\rightarrow \verb+00+ A \,\,|\,\, \lambda$
                 \item[\ \ \ ] $C\rightarrow \verb+1+ C \,\,|\,\, A$
                \end{enumerate}
          \item $G_2=(\{A,B,C,D\},\{\verb+0+,\verb+1+,\verb+2+\},R,A)$, onde $R$ consta das regras:
                \begin{enumerate}
                 \item[\ \ \ ] $A\rightarrow C \,\,|\,\, \verb+0+ CC \,\,|\,\, \verb+1+ DD$
                 \item[\ \ \ ] $B\rightarrow \verb+0+ B \,\,|\,\, \verb+0+ CD$
                 \item[\ \ \ ] $C\rightarrow \verb+1+ C \,\,|\,\, D$
                 \item[\ \ \ ] $D\rightarrow \verb+2+ D \,\,|\,\, C \,\,|\,\, \verb+2+$
                \end{enumerate}
        \end{list}
 \item Determine gram\'aticas na forma normal de Chomsky equivalentes \`as que voc\^e obteve na quest\~ao 5.

 \item Determine gram\'aticas na forma normal de Greibach equivalentes \`as que voc\^e obteve na quest\~ao 5.


\end{enumerate}
\end{document}



