\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{2}^{\mbox{\underline{o}}}$ semestre de 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Exame Especial} \hfill 02/01/97
 
\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 defini\c c\~oes recursivas para os seguintes conjuntos:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{0,1\}^* \,\,\,|\,\,\, \mbox{$w$ cont\'em $00$}\}$
        \item $\{0^i1^i \,\,\,|\,\,\, i\geq 0\}$
      \end{list}

 \item Obtenha express\~oes regulares que denotem os seguintes conjuntos:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{0,1\}^* \,\,\,|\,\,\, \mbox{$w$ cont\'em $00$}\}$
        \item $\{w\in\{0,1\}^* \,\,\,|\,\,\, \mbox{$w$ n\~ao cont\'em $00$}\}$
        \item $\{w\in\{0,1\}^* \,\,\,|\,\,\, \mbox{$w$ n\~ao termina com $01$}\}$
      \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 Seja a gram\'atica $G_1$:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aaS \,\,\,|\,\,\,
                  aaaS \,\,\,|\,\,\, \lambda$
      \end{enumerate}
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item Prove que $G_1$ \'e amb\'{\i}gua.
       \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G_1$.
      \end{list}

 \item Seja a gram\'atica $G_2$:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, BSA \,\,\,|\,\,\,
                  A$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\,
                  \lambda$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, Bba \,\,\,|\,\,\,
                  \lambda$
      \end{enumerate}
      Construa uma gram\'atica equivalente a $G_2$ que:
      \begin{itemize}
       \item seja essencialmente n\~ao contr\'actil; e
       \item n\~ao tenha regras recursivas \`a esquerda.
      \end{itemize}

 \item Construa aut\^omatos finitos determin\'{\i}sticos que reconhe\c cam cada
       um dos conjuntos da quest\~ao 2.

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

 \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\}^*\}$.
  
\end{enumerate}
 
\end{document}
\endinput
\end
 
 
