\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{Prova Suplementar/2} \hfill 30/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 Seja a linguagem $L=\{w0101 \,\,|\,\, w\in\{0,1\}^{*}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um aut\^omato finito determin\'{\i}stico que reconhe\c{c}a $L$.
        \item Construa uma gram\'atica regular que gere $L$, que n\~{a}o tenha mais
              de 6 regras.
        \item Construa uma express\~{a}o regular que denote $L$.
       \end{list}
 
 \item Seja a gram\'atica $G$:
       \begin{enumerate}
        \item[\ \ \ ] $S \rightarrow aSdddd \,\,|\,\, B$
        \item[\ \ \ ] $B \rightarrow bbBccc \,\,|\,\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O que \'{e} $L(G)$?
        \item Prove que $L(G)$ \'{e} o conjunto do item (a).
       \end{list}
 
 \item Seja a gram\'atica $H$:
       \begin{enumerate}
        \item[\ \ \ ] $S \rightarrow aBd \,\,|\,\, B$
        \item[\ \ \ ] $B \rightarrow BbB \,\,|\,\, C$
        \item[\ \ \ ] $C \rightarrow Cc \,\,|\,\, \lambda$
       \end{enumerate}
        Construa uma gram\'{a}tica na forma normal de Greibach equivalente a $L(H)$.
 
 \item Seja a gram\'atica $H$ da quest\~{a}o anterior. Prove que $L(H)$ n\~{a}o \'{e}
       regular.
 
 \item Especifique uma m\'aquina de Turing determin\'{\i}stica que reconhe\c{c}a a
       linguagem $L=\{www \,\,|\,\, w \in \{a,b\}^*\}$. N\~ao \'e necess\'ario
       construir a m\'aquina; basta especific\'a-la com precis\~ao e clareza.
       Pode ser utilizado qualquer modelo de m\'{a}quina, desde que determin\'{\i}stico.
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
 
