\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\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 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova} -- Turmas Z e F \hfill {08/07/2010}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 4 pontos cada uma, exceto a última, que vale 3 pontos.

\vspace*{2mm}
\begin{enumerate}
 \item Seja o seguinte diagrama de estados de uma MT com alfabeto de entrada $\{{\tt a},{\tt b}\}$:
       \begin{center} \small
       \begin{picture}(110,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir](1)(20,10){1}
        \node(2)(45,10){2}
        \node[Nmarks=r](3)(70,10){3}

        \drawedge[curvedepth=0](1,2){${\tt a}/\sqcup\;{\tt D}$}
        \drawedge[curvedepth=0](2,3){${\tt b}/\sqcup\;{\tt D}$}
        \drawloop[loopangle=0](3){$\sqcup/\sqcup\;{\tt D}$}
       \end{picture}
       \end{center}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Para quais palavras essa MT entra em \textit{loop\/}?
        \item Descreva a linguagem que ela reconhece por meio de uma express\~ao regular.
        \item Construa uma MT equivalente que nunca entre em \textit{loop}.
       \end{list}

 \item Seja a linguagem de express\~oes aritm\'eticas, EA, cuja sintaxe pode ser descrita
       pela gram\'atica $(\{E\},\{a,(,),+,*\},R,E)$, sendo $R$ constitu\'{\i}do das regras:
       \begin{enumerate}
        \item[\ ] $E\,\rightarrow\,E+E\,|\,E*E\,|\,(E)\,|\,a$
       \end{enumerate}
       Construa o diagrama de estados de uma MT de duas fitas que reconhe\c ca $L(\mbox{EA})$.

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

 \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 livre do contexto \'e recursiva.
        \item As linguagens de programa\c{c}\~ao (Java, C, Pascal etc.) n\~ao s\~ao recursivas.
        \item Se $L$ n\~ao \'e recursivamente enumer\'avel, $\overline{L}$ tamb\'em
              n\~ao \'e.
        \item Qualquer linguagem recursivamente enumer\'avel pode ser gerada por gram\'atica irrestrita.
        \item Uma m\'aquina de Turing n\~ao determin\'{\i}stica tem um poder computacional
              maior que o de uma determin\'{\i}stica.
        \item Uma m\'aquina de Turing n\~ao determin\'{\i}stica com duas fitas tem um poder computacional
              maior que o de uma determin\'{\i}stica de uma fita s\'o.
       \end{list}
\end{enumerate}

\end{document}
 
