\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova} \hfill 23/11/2010

\vspace*{4mm}

\noindent {Cada uma das quatro primeiras quest\~oes vale 3 pontos.}

\vspace*{1mm}
\begin{enumerate}
 \item Seja a linguagem $L=\{{\tt a},{\tt e},{\tt i},{\tt o},{\tt u}\}^+$.
       Construa uma MT padr\~ao:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item com \textit{um \'unico estado\/} que reconhe\c ca $L$;
        \item com \textit{uma \'unica transi\c{c}\~ao\/} que reconhe\c ca $\overline{L}$.
       \end{list}

 \item Construa o diagrama de estados de uma MT de duas fitas que reconhe\c ca
       \[\bigcup_{k\geq 1}\{{\tt 0}^m{\tt 1}^n \,|\, 1\leq m<n\}^k\mbox{.}\]
       Assim, cada palavra de entrada \'e da forma ${\tt 0}^{m_1}{\tt 1}^{n_1}
       {\tt 0}^{m_2}{\tt 1}^{n_2}\ldots{\tt 0}^{m_k}{\tt 1}^{n_k}$ para
       $k\geq 1$ e $1\leq m_i<n_i$ para todo $i=1,2,\ldots,k$.

 \item Construa uma gram\'atica irrestrita que gere $\{ww\,|\,w\in\{{\tt a},{\tt b}\}^+\}$.
       Caso a grama\'atica seja sens\'{\i}vel ao contexto, voc\^e ganha mais um ponto.

 \item Mostre que as linguagens recursivamente enumer\'aveis s\~ao fechadas sob
       concatena\c{c}\~ao.

 \item Responda sim ou n\~ao. Para cada resposta certa voc\^e ganha meio ponto
       e para cada resposta errada perde meio ponto:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Qualquer linguagem (subconjunto de $\Sigma^*$, onde $\Sigma$ \'e um
              alfabeto) \'e cont\'avel (finita ou infinita enumer\'avel), mas pode n\~ao ser
              recursivamente enumer\'avel.
        \item Se uma linguagem n\~ao \'e sens\'{\i}vel ao contexto, ent\~ao n\~ao \'e livre do contexto
        \item Qualquer linguagem recursiva pode ser reconhecida por aut\^omato finito.
        \item A linguagem de programa\c{c}\~ao Java n\~ao \'e recursiva.
        \item Se $L$ n\~ao \'e recursiva, $\overline{L}$ tamb\'em n\~ao \'e.
        \item Se $L$ n\~ao \'e recursivamente enumer\'avel, $\overline{L}$ tamb\'em
              n\~ao \'e.
        \item Uma m\'aquina de Turing n\~ao determin\'{\i}stica tem um poder computacional
              maior que o de uma determin\'{\i}stica.
        \item Seja ${\cal RE}$ a classe das linguagens recursivamente enumer\'aveis sobre
              o alfabeto $\Sigma$. A cardinalidade de ${\cal P}(\Sigma^*)-{\cal RE}$ \'e
              maior que a de ${\cal RE}$.\footnote{${\cal P}(\Sigma^*)$ \'e a classe de
              todas as linguagens de alfabeto $\Sigma$.}
       \end{list}

\end{enumerate}


\end{document}
 
