\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}
\newcounter{conta2}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova/especial} \hfill 26/09/2006

\vspace*{3mm}
\noindent {\bf Cada quest\~ao vale 3 pontos.}

\vspace*{2mm}
\begin{enumerate}

 \item Sejam $\Sigma=\{{\tt 0},{\tt 1}\}$,  $A=\Sigma^5$ e $B=\{{\tt 0}\}\Sigma^*$.
       Para cada uma das linguagens abaixo, d\^e uma propriedade necess\'aria
       e suficiente para que uma palavra perten\c ca \`a mesma:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A^*$.
        \item $B^+$.
        \item $A\cap B$.
        \item $AB$.
        \item $A^*\cap B^*$.
       \end{list}

 \item Descreva as linguagens abaixo, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando conjuntos finitos e \underline{apenas} as opera\c c\~oes:
       concatena\c c\~ao, uni\~ao, interse\c c\~ao e/ou fecho de Kleene.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de prefixo {\tt 01} e sufixo {\tt 10}.
        \item O conjunto das palavras com as subpalavras {\tt 010} ou {\tt 101} (ou ambas).
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w|$ \'e par e $w$ n\~ao cont\'em {\tt 11}$\}$.
       \end{list}

 \item Sobre gram\'aticas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma gram\'atica que gere $\{{\tt a}\}\{{\tt bb}\}^*\{{\tt c}\}$.
        \item Que linguagem \'e gerada pela gram\'atica $G$ definida a seguir?

              $G=(\{P,X\},\{{\tt a},{\tt b},{\tt c}\},R,P)$.
              \begin{enumerate}
               \item[$R$:] $P\,\rightarrow\,{\tt a} P {\tt a} \,|\, X$
               \item[\ ]   $X\,\rightarrow\, {\tt b} X {\tt c} \,|\, X {\tt c} \,|\, \lambda$
              \end{enumerate}
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para as linguagens
       dos \'{\i}tens (a) e (b) da quest\~ao 2. Apresente apenas o \underline{diagrama
       de estados} de cada AFD.

 \item Fa\c ca AFD's que reconhe\c cam: $X=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w|$ \'e
       par$\}$. e $Y=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$
       n\~ao cont\'em {\tt 11}$\}$. Bastam apenas os \underline{diagramas
       de estados}. Em seguida, obtenha o produto dos dois AFD's e explicite
       que estados finais ele deve ter para reconhecer
       $X\cap Y$ e $X\cup Y$.
\end{enumerate}

\end{document}
