\documentclass[11pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\pagestyle{empty}
\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill ICEx/UFMG \\
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Exame Especial}/Turma N \hfill 15/07/2009

\vspace*{3mm}
\begin{enumerate}
 \item (20 pontos) D\^{e} express\~{o}es regulares que denotem os conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de tamanho par sobre $\{{\tt a},{\tt b}\}$
              com exatamente um {\tt b}.
        \item O conjunto das palavras sobre $\{{\tt a},{\tt b},{\tt c}\}$ que n\~{a}o cont\^{e}m
              {\tt ab}.
       \end{list}

 \item (20 pontos) Mostre que os seguintes conjuntos n\~{a}o s\~{a}o regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^n\,|\, n \mbox{ \'e n\'umero primo}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^* \,|\,$ o n\'umero {\tt a}s em $w$ \'e primo$\}$.
       \end{list}

 \item (10 pontos) Seja $L$ a linguagem $\{w\in\{{\tt a},{\tt b}\}^*\,|\, $
       todo prefixo de $w$ tem mais {\tt b}s que {\tt a}s$\}$. Por exemplo,
       ${\tt bba}, {\tt bbbab}, {\tt bbbabaa}\in L$, mas $\lambda$, ${\tt a}, {\tt ba}\not\in L$.
       Construa um aut\^omato de pilha que aceite $L$.

 \item (20 pontos) Construa uma GLC para cada uma das linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n \,|\, m>n\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt a}^{k} \,|\, m>n \mbox{ ou } k>n\}$.
       \end{list}
       
 \item (20 pontos) Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\rightarrow\, {\tt a}S{\tt b} \,|\, S{\tt b}
                  \,|\, {\tt b}$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e $L(G)$?
        \item Construa duas deriva\c{c}\~{o}es mais a esquerda de {\tt abbb}.
        \item Construa as \'{a}rvores de deriva\c{c}\~{a}o para as deriva\c{c}\~{o}es da parte (b).
        \item Construa uma GLC n\~{a}o amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item (10 pontos) Prove que toda linguagem recursivamente enumer\'{a}vel
       \'{e} aceita por uma MT $M$ tal que $w\in L(M)$ se, e somente se, $M$ para se
       sua entrada for $w$.

\end{enumerate}

\end{document}
\endinput
\end
