\documentclass[11pt,a4paper]{report}

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

\pagestyle{empty}
\newcounter{conta}

\begin{document}
 
\vspace*{1cm}
\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 2013 \\
Professor: Newton José Vieira \\
\noindent{\em Segunda prova}    \hfill 22/10/2013

\vspace*{3mm}
\noindent Cada uma das 4 primeiras questões tem peso 4 e cada uma das duas últimas tem peso 3.
\begin{enumerate}
 \item Para cada linguagem a seguir, construa um APD que a reconheça, se possível. Se não for possível,
       construa um APN. Critério de reconhecimento: por estado final \textbf{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=\{\verb+a+^m\verb+b+^n\verb+c+^p \,|\, m\geq n \textbf{ ou } m\geq p\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma GLC que gere $L$.
				\item Mostre que a GLC construída é ambígua ou apresente uma argumentação convincente de que não é.
       \end{list}

 \item Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Existe gramática regular ambígua.
				\item Não existe linguagem regular inerentemente ambígua.
       \end{list}

 \item Prove que $L=\{\verb+a+^m\verb+b+^n\verb+c+^p \,|\, m\geq n \textbf{ e } m\geq p\}$ não é
       livre do contexto.

 \item Dada uma GLC qualquer, como se obtém uma GLC equivalente sem regras unitárias? Descreva de forma \textbf{precisa}
       um método para tal obtenção.  (Regras unitárias são da forma $A\,\rightarrow\,B$, em que $A$ e $B$ são variáveis.)

 \item Apresente exemplos de LLCs $L_1$ e $L_2$ tais que $L_1\cap L_2$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item É regular.
        \item É LLC, mas não é regular.
				\item Não é LLC.
       \end{list}
\end{enumerate}

\end{document}
