\documentclass[11pt]{report}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Exame Especial} \hfill \textbf{Duração: 1h 40min} \hfill 28/1/2013

\vspace*{3mm}
\noindent \textbf{Valores:} 10 pontos cada questão.
\vspace*{3mm}
\begin{enumerate}
 \item Dê uma expressão regular que denote o conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ com número ímpar de
       símbolos e que contenham pelo menos um {\tt 0}.

 \item Faça um autômato finito (de qualquer tipo) que reconheça $AB$, sendo
       $A=\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ tem número ímpar de {\tt a}s$\}$ e
			 $B=\{w\in\{{\tt a},{\tt c}\}^*\,|\, w$ tem número par de {\tt a}s$\}$.

 \item Mostre como obter um AFN equivalente a um AFD dado.

 \item Sabendo que $\{a^nb^m \,|\, n<m\}$ não é linguagem regular, mostre que $\{w\in\{a,b\}^*\,|\,
        n_b(w)>n_a(w)\}$ não é regular. ($n_s(w)$ é a quantidade do símbolo $s$ em $w$.)

 \item Construa um autômato de pilha determinístico que aceite  $\{a^mb^n \,|\, m<n\}$.
 
 \item Construa uma gramática livre do contexto que gere $\{{\tt a}^m{\tt b}^n \,|\, m>2n\}$.

 \item Seja $G$ a gramática
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\rightarrow\, {\tt a}S{\tt b} \,|\, X$
        \item[\ ] \hspace*{1cm}$X \,\rightarrow\, XX \,|\, {\tt a}$
       \end{enumerate}
       Mostre que $G$ é ambígua e construa uma gramática não ambígua equivalente a $G$.

 \item Mostre como detectar todas as variáveis inúteis de uma gramática livre do contexto.

 \item Faça uma gramática sensível ao contexto que gere $\{a^nb^ka^n \,|\, k>n\}$
 
 \item Mostre como obter uma máquina de Turing que aceite por parada equivalente a uma que aceite por parada
       em estado final.
\end{enumerate}

\end{document}
\endinput
\end
