\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 2018 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Segunda Prova} \hfill 5/6/2018

\vspace*{3mm}
\begin{enumerate}
 \item (3 pontos) Prove que $\{xx^r \,|\, x\in \{{\tt 0},{\tt 1}\}^*\}$ não é linguagem regular usando o teorema da invariância à direita ou o lema do bombeamento.

 \item (3 pontos) Sejam $L_1=\{{\tt a}^n \,|\, n\geq 1000\}$ (regular), $L_2=\{{\tt a}^n{\tt b}^k \,|\, n\geq k\}$ (não regular) e $L_3=\{{\tt a}^n \,|\, n \mbox{ é número primo}\}$ (não regular). Para cada linguagem a seguir, mostre que ela é regular ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_2-L_1$;
        \item $L_3-L_1$;
        \item $L_1\cap L_3$.
       \end{list}

 \item (4 pontos) Construa uma expressão regular que denote a linguagem $$\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w) \mbox{ é par e } n_{\tt b}(w) \mbox{ é par}\}\mbox{.}$$

 \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) Construa GLCs que gerem:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^m{\tt b}^n \,|\, m\not=n\}$;
        \item $L_2=\{{\tt a}^{m+n}{\tt b}^{m}{\tt c}^{n} \,|\, m \mbox{ é par e } n \mbox{ é ímpar}\}$;
	      \item $L_1\cup L_2\cup (L_1L_2L_2)^+\cup (L_2L_1L_1)^+$.
       \end{list}


 \item (3 pontos) Seja a gramática $G$ com as regras:
      \begin{enumerate}
       \item[\ ] $P\,\rightarrow\, A \,|\, B$
       \item[\ ] $A\,\rightarrow\, {\tt a}A{\tt a} \,|\, \lambda$
       \item[\ ] $B\,\rightarrow\, {\tt b}B{\tt bb} \,|\, \lambda$
      \end{enumerate}
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item Mostre que $G$ é ambígua.
       \item Remova a ambiguidade de $G$.
      \end{list}

\vfill
\hfill {\footnotesize \emph{Última questão no verso}} $\Rightarrow$
\pagebreak

 \item (3 pontos) Seja a gramática:
       \begin{enumerate}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
	      \item[\ ] $P\,\rightarrow\, A A A  \,|\,  B$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, B \,|\, BC$
	      \item[\ ] $B\,\rightarrow\,\lambda$
	      \item[\ ] $C\,\rightarrow\, BC$
	     \end{enumerate}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Se existirem símbolos inúteis, elimine-os.
        \item Elimine regras $\lambda$.
        \item Elimine variáveis inúteis.
        \item Elimine regras unitárias.
        \item Obtenha uma GLC equivalente na forma normal de Chomsky.
       \end{list}
\end{enumerate}

\end{document}
