\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} \hfill 14/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,\},\{{\tt a},{\tt b}\},\{{\tt a},{\tt b},\langle,
       \sqcup\},\langle, \sqcup,\delta,\{1\},\{2,3\})$, onde $\delta$ \'e
       como segue:
       \begin{enumerate}
        \item[\ ] $\delta(1,{\tt a})=[2,\sqcup,{\tt D}]$
        \item[\ ] $\delta(1,{\tt b})=[3,{\tt b},{\tt D}]$
        \item[\ ] $\delta(2,{\tt a})=[2,\sqcup,{\tt D}]$
        \item[\ ] $\delta(3,{\tt b})=[1,{\tt b},{\tt E}]$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que palavras fazem $M$ parar no estado 1?
        \item Que palavras fazem $M$ parar no estado 2?
        \item Que palavras fazem $M$ parar no estado 3?
        \item Que palavras fazem $M$ entrar em {\em loop\/}?
        \item Que linguagem \'e reconhecida por $M$?
       \end{list}

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

 \item Construa uma gram\'atica sens\'{\i}vel ao contexto que gere a linguagem
       $\{w{\tt b}w \;|\; w\in\{{\tt a},{\tt c}\}^*\}$.

 \item Dado um AFD $M=(E,\Sigma,\delta,i,F)$, especifique como seria uma MT
       $M'=(E',\Sigma,\Gamma,\langle,\sqcup,\delta',i',F')$ que reconhece
       $L(M)$. Para isto, obviamente basta especificar o que seria $E'$,
       $\Gamma$, $\delta'$, $i'$ e $F'$.

 \item Preencha o que est\'a vago no seguinte quadro:
       \begin{center}
        \begin{tabular}{|c|c|c|} \hline
         {\em Linguagem} & {\em Reconhecedor}    & {\em Gram\'atica} \\ \hline\hline
         regular         &                       &             \\ \hline
                         & aut\^omato com pilha  &             \\ \hline
                         &                       & irrestrita  \\ \hline
        \end{tabular}
       \end{center}
       Existe algum outro tipo de linguagem que n\~ao esteja mencionado no
       quadro acima? Se sim, qual?
 
\end{enumerate}

\end{document}
 
