\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 1995
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Exame Especial} \hfill 12/07/95
 
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 40 minutos.
 \item[Valores das quest\~{o}es:] a quest\~{a}o 1 vale 10 pontos, e as quest\~{o}es
         restantes valem 15 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 $G$:
       \begin{enumerate}
        \item[\ \ \ ] $S \rightarrow AB \,\,|\,\, BCS$
        \item[\ \ \ ] $A \rightarrow aA \,\,|\,\, C$
        \item[\ \ \ ] $B \rightarrow bbC \,\,|\,\, b$
        \item[\ \ \ ] $C \rightarrow cC \,\,|\,\, \lambda$
       \end{enumerate}
       Construa uma gram\'{a}tica $G'$ equivalente a $G$, essencialmente n\~{a}o
       contr\'{a}ctil e sem regras de cadeias ({\it chain rules\/}).
 
 \item Prove que $\{a^nb^{n^2} \,\,|\,\, n \geq 0\}$ n\~{a}o \'{e} linguagem livre do
       contexto.
 
 \item Seja a linguagem $A=\{a^nb^nc^n \,\,|\,\, n > 0\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma gram\'{a}tica sens\'{\i}vel ao contexto que gere $A$.
        \item Construa um at\^{o}mato linear limitado que aceite $A$.
       \end{list}

 \item Construa uma m\'aquina de Turing determin\'{\i}stica que reconhe\c{c}a a linguagem
       \[\{ww \,\,|\,\, w \in \{a,b\}^*\}\mbox{.}\] Pode ser utilizado qualquer
       modelo de m\'{a}quina de Turing (desde que determin\'{\i}stica).
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
 
