\documentclass[12pt, a4paper]{report}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{1cm}
\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{2}^{\mbox{\underline{o}}}$ semestre de 2001
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent {\bf Prova Suplementar} \hfill 22/04/02
 
\vspace*{3mm}
\noindent {Cada item de cada quest\~ao vale 3 pontos.}

\begin{enumerate}

 \item Construa aut\^omatos finitos determin\'{\i}sticos para reconhecer as se\-guin\-tes
       linguagens de alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] O conjunto das palavras cujo pen\'ultimo s\'{\i}mbolo \'e 1.
        \item[(b)] $\{w010\,\,|\,\, w\in\{0,1\}^*\}$.
        \item[(c)] $(\{1\}\cup\{0\}\{1\}^*\{0\})^*$.
       \end{enumerate}

 \item Construa um aut\^omato finito n\~ao determin\'{\i}stico que
       reconhe\c ca a linguagem: \[\{x\verb+1+y \,\,|\,\, x,y\in\{\verb+0+,\verb+1+\}^*
       \mbox{ e } \eta(y)\,\mbox{\em mod\/}\,3 = 1\}\mbox{.}\]
       onde $\eta(y)$ \'e o n\'umero representado por $y$ na base 2 e {\em mod\/} \'e o
       operador ``resto da divis\~ao''.

 \item Encontre express\~oes e gram\'aticas regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, |w|>1 \mbox{ e $w$ cont\'em } \verb+1+\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, \verb+0+'s
               \mbox{ n\~ao ocorrem em posi\c c\~oes \'{\i}mpares}\}$
       \end{list}

 \item Seja a gram\'atica $G=(\{P,A\},\{\verb+a+,\verb+b+,\verb+c+,\verb|+|\},R,P)$,
       onde $R$ consta das regras:
       \begin{enumerate}
        \item[\ ] $P\,\,\rightarrow\,\,\verb|a+| P \,\,|\,\, A$
        \item[\ ] $A\,\,\rightarrow\,\, P\verb|+b| \,\,|\,\, \verb|c|$
       \end{enumerate}
       Qual \'e a linguagem gerada por $G$? Mostre que $G$ \'e amb\'{\i}g\"ua usando a
       {\em menor\/} palavra poss\'{\i}vel. Construa uma gram\'atica livre do contexto
       equivalente a $G$ n\~ao amb\'{\i}g\"ua.

 \item Mostre que sim ou que n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item As linguagens recursivas s\~ao fechadas sob diferen\c ca.
        \item As linguagens recursivamente enumer\'aveis s\~ao fechadas
              sob di\-fe\-ren\-\c ca.
       \end{list}

\end{enumerate}

\end{document}
