\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{2}^{\mbox{\underline{o}}}$ semestre de 2017 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Terceira Prova} \hfill 5/12/2017

\vspace*{3mm}
\begin{enumerate}
 \item Para cada linguagem a seguir, mostre que ela é ou não é LLC:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{{\tt a}^n{\tt b}^k{\tt c}^n\,|\, n\geq 0 \mbox{ e } k \mbox{ é ímpar}\}$.
        \item $\{{\tt a}^n{\tt b}^k{\tt c}^n\,|\, n\geq 0 \mbox{ e } k \mbox{ é primo}\}$.
       \end{list}
 \item Escreva uma MT \underline{não determinística} de duas fitas que reconheça
       $$\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,n_{\tt 0}(w)<n_{\tt 1}(w)\}\mbox{.}$$
       Procure obter uma MT com o \underline{menor número de estados} possível.
 \item Construa uma gramática sensível ao contexto que gere
       $\{{\tt 0}^n{\tt 1}^k{\tt 0}^n{\tt 1}^k\,|\, n\geq 0 \mbox{ e } k\geq 1\}$.

 \item Mostre que é possível ou não o complemento de uma linguagem \underline{não LRE} ser 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 $M$ reconhece alguma
				      das palavras de $F$;
			  \item Dada uma MT $M$, determinar se ela é a única que reconhece $L(M)$;
			  \item Dada uma MT $M$, determinar se ela reconhece alguma palavra com o símbolo {\tt 0}.
       \end{list}

\end{enumerate}
\end{document}
