\documentclass[12pt]{report}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{3cm}

\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Departamento de Ci\^encia da Computa\c c\~ao \hfill ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill
                            $1^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Quarta Prova/Suplementar} \hfill 19/08/2003 \hfill {\bf Dura\c c\~ao: 1h:30m} \\
\noindent {\bf Turmas B e G}

\vspace*{1mm}
\noindent {\bf Cada quest\~ao vale 3 pontos.}

\vspace*{1mm}
\begin{enumerate}
 \item Seja a MT $M=(\{1,2,3,4\},\{{\tt a},{\tt b}\},\{{\tt a},{\tt b},\langle,
       \sqcup\},\langle, \sqcup,\delta,\{1\},\{4\})$, n\~ao determin\'{\i}stica,
       onde $\delta$ \'e como segue:
       \begin{enumerate}
        \item[\ ] $\delta(1,{\tt a})=[1,{\tt a},{\tt D}]$
        \item[\ ] $\delta(1,{\tt a})=[2,\sqcup,{\tt D}]$
        \item[\ ] $\delta(1,{\tt a})=[3,{\tt a},{\tt D}]$
        \item[\ ] $\delta(2,{\tt a})=[2,{\tt a},{\tt D}]$
        \item[\ ] $\delta(2,\sqcup)=[4,\sqcup,{\tt E}]$
        \item[\ ] $\delta(3,{\tt a})=[3,{\tt a},{\tt D}]$
        \item[\ ] $\delta(3,{\tt b})=[4,\sqcup,{\tt E}]$
        \item[\ ] $\delta(4,{\tt a})=[4,\sqcup,{\tt E}]$
       \end{enumerate}
       Para quais palavras existem computa\c c\~oes que terminam no estado:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item 1?
        \item 2?
        \item 3?
        \item 4?
        \item Que linguagem \'e reconhecida por $M$?
       \end{list}

 \item Construa uma MT de duas fitas que reconhe\c ca
       $\{{\tt a}^n{\tt b}^k{\tt a}^n \;|\; n,k\geq 0\}$, de tal forma que
       ela d\^e uma \'unica passada sobre a palavra de entrada.

 \item Construa uma gram\'atica irrestrita que gere
       $\{{\tt a}^n{\tt b}^k{\tt a}^n{\tt b}^k \;|\; n\geq 0\}$.

 \item Dada uma MT $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i,F)$, especifique
       como seria uma MT $M'=(E',\Sigma,\Gamma',\langle,\sqcup,\delta',i',F')$
       que reconhece $L(M)$ por estado final, isto \'e, tal que $L_F(M')=L(M)$.

 \item Defina o que \'e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Uma gram\'atica sens\'{\i}vel ao contexto.
        \item Um aut\^omato linearmente limitado.
        \item Uma linguagem recursiva.
       \end{list}

\end{enumerate}

\end{document}
 
