\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
%\usepackage{gastex}
%\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova} -- Turma W\hfill {04/4/2013}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} as questões 1 e 2 valem 3 pontos cada uma, e as restantes 6 pontos cada uma.

\vspace*{2mm}
\begin{enumerate}
 \item Qual linguagem abaixo difere das outras? Justifique sua resposta.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{0\}^*$
        \item $\{\lambda,0\}^*$
        \item $\{0\}^+$
        \item $\{\lambda,0\}^+$
       \end{list}

 \item Seja $G$ a gramática de regras:
       \begin{quote}
        $P\,\rightarrow\, 0 P 1\,|\, \lambda$
       \end{quote}
       Em quantos passos (aplicações de regras) é derivada uma palavra $0^n1^n$? Justifique sua resposta.

 \item Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas \textit{conjuntos finitos} e opera\c{c}\~oes de \textit{uni\~ao}, \textit{interse\c{c}\~ao},
       \textit{complementa\c{c}\~ao}, \textit{concatena\c c\~ao} e \textit{fecho de Kleene}. Procure obter uma
       descri\c c\~ao bem concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de prefixo {\tt 01}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 01} como sufixo.
			\end{list}

 \item Construa AFDs para as linguagens da questão anterior.

 \item Construa um AFD que reconheça $AB$, sendo:
			 \begin{itemize}
			  \item $A=\{w\in\{a,b\}^*\,|\, w \mbox{ tem número ímpar de $a$s}\}$, e
			  \item $B=\{w\in\{a,c\}^*\,|\, w \mbox{ tem número par de $a$s}\}$.
			 \end{itemize}
			 Comece construindo AFDs para $A$ e $B$; depois obtenha um AFN$\lambda$ para $AB$ a partir dos dois; em seguida
			 transforme o AFN$\lambda$ em AFN; e, finalmente, obtenha o AFD a partir do AFN.
\end{enumerate}


\hrule
\vspace*{.3mm}
\hrule
\begin{quote}
 AFD: autômato finito determinístico \\
 AFN: autômato finito não determinístico \\
 AFN$\lambda$: autômato finito não determinístico com transição $\lambda$
\end{quote}

\end{document}
