\documentclass[11pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
%\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage         {amsfonts}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2017 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Segunda Prova} \hfill 7/11/2017

\vspace*{3mm}
\begin{enumerate}
 \item (3 pontos) Prove, usando o teorema da invariância à direita ou o lema do bombeamento, que a linguagem 
       $\{{\tt 0}^na{\tt 0}^n\,|\, a\in \{{\tt 0},{\tt 1}\} \mbox{ e } n\in\mathbb{N}\}$ não é regular.
 \item (3 pontos) Sejam $L_1=\{{0}^{n^2} \,|\, n \in\mathbb{N}\}$ (não regular) e $L_2=\{{\tt 0}^k\}\{{\tt 0}\}^*$ (regular), em que
       $k$ é uma constante. Para cada linguagem a seguir, mostre que ela é regular ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1-L_2$;
        \item $L_1\cap L_2$;
        \item $L_1\cup L_2$.
       \end{list}
 \item (3 pontos) Construa uma expressão regular que denote $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ não termina com {\tt cc}}\}$.
 \item (3 pontos) Construa um APD para a linguagem da questão 1, se possível. Se não for possível, construa APN.
 \item (4 pontos) \color[rgb]{0,0,0}Construa GLCs que gerem: 
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^n{\tt b}^{2n+k+1}{\tt c}^{3k} \,|\, n,k\in\mathbb{N}\}$;
        \item $L_2=\{{\tt a}^m{\tt b}^n{\tt c}^k \,|\, m>n+k\}$;
	      \item $(L_1L_2)^*$.
       \end{list}
 \item (3 pontos) Seja a gramática $G$ com as regras:
      \begin{enumerate}
       \item[\ ] $A\,\rightarrow\, {\tt a}A \,|\, {\tt b}B \,|\, \lambda$
       \item[\ ] $B\,\rightarrow\, {\tt b}B \,|\, A$
      \end{enumerate}
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item Mostre duas árvores de derivação ou DMEs para a menor palavra para a qual existam duas árvores de derivação.
       \item Remova a ambiguidade de $G$.
      \end{list}
 \item (4 pontos) Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ]$S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1}$
        \item[\ ]$A \,\rightarrow\, {\tt 1}A{\tt 1} \,|\, S \,|\, \lambda$
       \end{enumerate}
       Obtenha GLCs equivalentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item na forma normal de Chomsky;
        \item na forma normal de Greibach.
       \end{list}
\end{enumerate}

\end{document}
