\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{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Exame Especial} \hfill \textbf{Duração: 1h 30min} \hfill 10/7/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}\}$ que não contêm
       {\tt 00}. Expressão regular sintaticamente incorreta não será aceita.

 \item Mostre como construir um autômato finito que, dados dois AFDs $M_1$ e $M_2$, reconheça $L(M_1)\cap L(M_2)$.

 \item Mostre como obter um AFN equivalente a um AFN$\lambda$ dado.

 \item Construa um autômato de pilha que aceite $\{a^mb^na^m \,|\, m,n\geq 0\}$.
 
 \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\, SS \,|\, X$
        \item[\ ] \hspace*{1cm}$X \,\rightarrow\, aXb \,|\, \lambda$
       \end{enumerate}
       Mostre que $G$ é ambígua e construa uma gramática não ambígua equivalente a $G$.

 \item Mostre como eliminar toda regra $\lambda$ de uma gramática livre do contexto.
 
 \item O que é uma gramática sensível ao contexto? Que tipo de máquina reconhece linguagem sensível ao contexto?

 \item Construa uma máquina de Turing que aceite $a^*$.

 \item Qual a diferença entre linguagem recursiva e recursivamente enumerável?
\end{enumerate}

\hrule
\vspace{.5mm}
\hrule

\vspace{5mm}
\noindent AFD: autômato finito determinístico. \\
AFN: autômato finito determinístico não determinístico. \\
AFN$\lambda$: autômato finito não determinístico com transições $\lambda$.
\end{document}
\endinput
\end
