\documentclass[11pt,a4paper]{book}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{10mm}
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Prova Suplementar} \hfill 30/11/2010

\vspace*{3mm}
\begin{flushleft}
Dura\c{c}\~ao: 1 hora e 40 minutos.
\end{flushleft}

\begin{enumerate}
 \item (8 pontos) Construa:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item um AFD, e
        \item uma express\~ao regular
       \end{list}
       para a linguagem $$\{w\in \{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ cont\'em número ímpar de {\tt a}s
       e não contém a subpalavra {\tt abc}}\}\mbox{.}$$ No item (a), apenas desenhe o diagrama de estados.
       No item (b), n\~ao será aceita expressão regular com sintaxe incorreta.

 \item (5 pontos) Apresente um diagrama de estados para um AFN que reconhe\c{c}a a linguagem
       $$L=\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, {\tt 000} \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 (5 pontos) Construa uma gramática livre do contexto que gere $\{{\tt 0}^k{\tt 1}^n \,|\, k \mbox{ é ímpar e } k\not=n\}$.

 \item (6 pontos) Seja $L$ uma linguagem {\em n\~ao\/} recursivamente enumer\'avel. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $F$ \'e finita, $L-F$ n\~ao \'e recursivamente enumer\'avel.
        \item Se $R$ \'e regular, $L-R$ pode ser regular ou n\~ao.
        \item $\overline{L}$ pode ser recursivamente enumer\'avel.
       \end{list}

 \item (6 pontos) Para cada PD abaixo, mostre que o mesmo \'e decid\'{\i}vel ou que n\~ao
       \'e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dadas uma linguagem livre do contexto $L$ e uma  linguagem
              regular $R$, determinar se $L=R$.
        \item Dadas uma linguagem livre do contexto $L$ e uma  linguagem
              regular $R$, determinar se $L$ e $R$ s\~ao disjuntas.
       \end{list}
\end{enumerate}

\end{document}