\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}
\noindent Pós-Graduação em Ciência da Computação \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2018 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Terceira Prova} \hfill 10/7/2018

\vspace*{3mm}
\begin{enumerate}
 \item Mostre que a linguagem $\{R\langle M\rangle\,|\, L(M)\not=\emptyset\}$ é LRE e que $\{R\langle M\rangle\,|\, L(M)=\emptyset\}$ não é LRE.

 \item Para cada PD a seguir, mostre que o mesmo é indecidível ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Dados uma MT $M$ e um estado $e$ de $M$, determinar se a computação de $M$ para a entrada
				      {\tt 01} atinge o estado $e$;
        \item Dados uma MT $M$ e um conjunto finito de palavras $F$, determinar se existe $w\in F$ tal que $w\in L(M)$;
			  \item Dada uma MT $M$, determinar se ela reconhece alguma palavra com o símbolo {\tt 0}.
			  \item Dadas MTs $M_1$ e $M_2$, determinar se $\lambda\in L(M_1)\cap L(M_2)$.
       \end{list}

 \item Para cada PD a seguir, mostre que o mesmo é indecidível ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
				\item Dada uma gramática livre do contexto $G_1$ e uma gramática regular $G_2$, determinar se $L(G_1)=L(G_2)$.
				\item Dadas duas gramáticas livres do contexto $G_1$ e $G_2$, determinar se $L(G_1)\cap L(G_2)$ é finito.
       \end{list}

\end{enumerate}
\end{document}
