\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 1995
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Quarta Prova} \hfill 29/06/95
 
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 30 minutos.
 \item[Valores das quest\~{o}es:] 5 pontos cada uma.
\end{description}
 
\begin{enumerate}
 
 \item Construa uma m\'{a}quina de Turing padr\~{a}o cujas computa\c{c}\~{o}es sejam da forma
       \begin{enumerate}
        \item[\ \ \ ] $q_0BuB \stackrel{*}{\vdash} q_{i}BvB$
       \end{enumerate} 
       sendo $u\in\{a,b\}^{*}$, $v$ o {\it string\/} obtido pela duplica\c{c}\~{a}o
       de cada $a$ em $u$, e $q_{i}$ qualquer estado em que a m\'{a}quina pare.
       Por exemplo: $q_0BbbabaabB \stackrel{*}{\vdash} q_{i}BbbaabaaaabB$.
       
 \item Construa uma m\'{a}quina de Turing padr\~{a}o que reconhe\c{c}a $\{ww^{R} \,\,|
       \,\, w\in \{a,b\}^{*}\}$. O alfabeto de fita deve ser $\Gamma=\{a,b,B\}$.
 
 \item Construa uma m\'{a}quina de Turing n\~{a}o determin\'{\i}stica de 2 fitas que
       reconhe\c{c}a a linguagem $\{ww^{R} \,\,|\,\, w\in \{a,b\}^{*}\}$. Uma
       computa\c{c}\~{a}o com entrada $u$ deve terminar ap\'{o}s, no m\'{a}ximo, $|u|+2$
       transi\c{c}\~{o}es. ($|u|$ \'{e} o tamanho de $u$.) 
 
 \item Construa uma gram\'{a}tica irrestrita que gere $\{ww \,\,|\,\,
       w\in \{a,b\}^{*}\}$.
 
 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Prove que o conjunto $L=\{ww^R \,\,|\,\, w\in \{a,b\}^{+}\}$ \'{e} uma
              linguagem sens\'{\i}vel ao contexto.
        \item O conjunto $L=\{ww \,\,|\,\, w\in \{a,b\}^{+}\}$ \'{e} uma linguagem
              sens\'{\i}vel ao contexto? Por que?
       \end{list}

\end{enumerate}                                                          

 
\end{document}
\endinput
\end
 
 
