\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\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 1997
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Exame Especial} \hspace*{2cm} 13h30min \hspace*{2cm}
 11/07/97 \hspace*{2cm} Sala 1017
 
\begin{description}
 \item[Dura\c{c}\~{a}o:] 2 horas.
 \item[Valores das quest\~{o}es:] 10 pontos cada uma.
\end{description}
 
\begin{enumerate}

 \item D\^{e} express\~{o}es regulares para os conjuntos dos {\it strings\/}
       sobre $\{a,b,c,d,e\}$ (a) de tamanho menor que 3, (b) de tamanho 3,
       e (c) de tamanho maior que 3.

 \item Seja a linguagem \[L=\{w \in \{a,b,c\}^* \,\,|\,\, \mbox{$w$ cont\'{e}m
       um n\'{u}mero \'{\i}mpar de ocorr\^{e}ncias do {\it substring\/}
       $ab$}\}\mbox{.}\]
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um aut\^omato finito determin\'{\i}stico que
              reconhe\c{c}a $L$.
        \item Determine uma express\~{a}o regular que denote $L$, a partir do
              aut\^{o}mato, utilizando o m\'{e}todo do grafo de express\~{o}es.
       \end{list}

 \item Prove que $\{ww \,\,|\,\, w \in \{a,b\}^*\}$ n\~ao \'e linguagem regular.

 \item Seja a gram\'atica
       \begin{enumerate}
        \item[\ \ \ ] $G$: $E \rightarrow E + E \,\,|\,\, E * E \,\,|\,\, a$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ \'e amb\'{\i}gua.
	\item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}
 
 \item Construa gram\'aticas para:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^j \,\,\,|\,\,\, i>j\}$
        \item $\{a^ib^j \,\,\,|\,\,\, j\leq i \leq 2j\}$
      \end{list}

 \item Construa um aut\^omato a pilha ({\it push-down automaton\/}) que
       reconhe\c ca $\{a^ib^j \,\,\,|\,\,\, i\not=j\}$.

 \item Construa uma m\'aquina de Turing que, recebendo como entrada um n\'umero
       representado em bin\'ario, some 1 ao mesmo e retorne o cabe\c cote de
       leitura para a posi\c c\~ao inicial. Exemplos:
       \begin{itemize}
        \item $q_0 B 1010 B \stackrel{*}{\vdash} q_4 B 1011 B$
        \item $q_0 B 1011 B \stackrel{*}{\vdash} q_4 B 1100 B$
        \item $q_0 B 111 B \stackrel{*}{\vdash} q_4 B 1000 B$
      \end{itemize}

 \item Construa uma gram\'atica irrestrita que gere a linguagem
       $\{ww \,\,\,|\,\,\, w\in \{a,b\}^*\}$.
 
 \item Especifique uma m\'aquina de Turing determin\'{\i}stica de 3 fitas
       que reconhe\c{c}a a linguagem $L=\{ww^Rw \,\,|\,\, w \in \{a,b\}^*\}$.
       N\~ao \'e necess\'ario construir a m\'aquina; basta especific\'a-la
       com precis\~ao e clareza.
 
 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
 
        \item Utilizando redu\c{c}\~ao de um problema a outro, como \'e que se
	      prova que um problema \'e:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
	       \item decid\'{\i}vel;
	       \item indecid\'{\i}vel?
	      \end{list}
        \item Que caracter\'{\i}sticas deve ter a linguagem de
	      representa\c{c}\~ao de um problema para que ele seja:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
	       \item decid\'{\i}vel;
	       \item indecid\'{\i}vel?
	      \end{list}
       \end{list}
 
\end{enumerate}
 
\end{document}
\endinput
\end

 
