\documentclass[12pt,a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{gastex}
\usepackage[usenames]{color}

\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 2014 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Prova Suplementar}

\vspace*{3mm}
\noindent Cada questão vale 7 pontos.

\vspace*{3mm}
\begin{enumerate}
 \item Apresente um diagrama de estados de um AFD que reconheça $(000+1)^*(00+11)$.
 \item Apresente um diagrama de estados de um AFN que reconheça a linguagem
       $$L=\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, {\tt 001} \mbox{ não é sufixo de } w\}$$ e que tenha as
       seguintes características:
       \begin{itemize}
        \item tem um único estado final; e
        \item para cada $w\in L$ existe uma única computação de sucesso.
			 \end{itemize}
  \item Se a linguagem $\{w\in\{{\tt a},{\tt b}\}^*\,|\, n_{\tt a}(w) \mbox{ é par e } n_{\tt b}(w) \mbox{ é primo}\}$ for 
       livre do contexto, prove que ela não é regular; caso contrário, prove que ela não é livre do contexto. ($n_{\tt a}(w)$
			 é o número de {\tt a}s em $w$.)
 \item Seja $L=\{{\tt 0}^k{\tt 1}^n\,|\, k \mbox{ é ímpar e } k\not=n\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma gramática livre do contexto que gere $L$.
        \item Para cada variável $X$ da gramática, dê $L(X)=\{w\in\{{\tt a},{\tt b}\}^*\,|\,X\stackrel{*}{\Rightarrow} w\}$.
	     \end{list}
 \item Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma GLC $G$, determinar se $L(G)\subseteq \{{\tt 1}\}^*$.
        \item Dada uma MT $M$ e um AFD $A$, determinar se $L(M)\subseteq L(A)$.
       \end{list}
\end{enumerate}

\end{document}
