
\documentstyle[12pt]{article}
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas ne-nhum}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos Te\'oricos da Computa\c c\~ao}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2000
 
\noindent Professor: Newton Jos\'{e} Vieira

\noindent {\bf Primeira Prova} \hfill Data: 28/09/2000

\vspace*{2mm}
\noindent \underline{Escolha 6 quest\~oes.} \underline{Cada uma vale 2,5 pontos.}

\begin{enumerate}
 \item Responda sem justificar:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Sejam $A=\{\lambda,\verb+a+\}$ e $B=\{\verb+a+,\verb+b+\}$. Quantos elementos tem
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item $A^nB$
               \item $AB^n$
               \item $A^nB^n$
              \end{list}
              para $n\geq 0$ arbitr\'ario?
        \item Simplifique:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item $(A^*)^+$
               \item $(A^+)^*$
               \item $A^*\cap A^+$
               \item $A^*A^+$
               \item $A^+-A^*$
               \item $A^*-A^+$
              \end{list}
       \end{list}

 \item Descreva as seguintes linguagens sobre o alfabeto $\{\verb+0+,\verb+1+\}$, usando apenas as
       opera\c c\~oes de {\em concatena\c c\~ao\/}, {\em uni\~ao\/} e/ou {\em fecho de Kleene\/}
       aplicadas a conjuntos finitos espec\'{\i}ficos de palavras de $\{\verb+0+,\verb+1+\}^*$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item o conjunto das palavras com, no m\'aximo, um \verb+0+;
        \item o conjunto das palavras com n\'umero \'{\i}mpar de \verb+0+'s;
        \item o conjunto das palavras cujo antepen\'ultimo s\'{\i}mbolo \'e \verb+0+, {\em caso este
              exista\/}.
       \end{list}

 \item Seja $\Sigma=\{\verb+a+\}$. Mostre que o conjunto $\Sigma^*$ \'e enumer\'avel, e que o conjunto 
       ${\cal P}(\Sigma^*)$ n\~ao \'e enumer\'avel.

 \item Sejam $L_1$ e $L_2$ linguagens sobre um certo alfabeto $\Sigma$ tais que $L_1\subseteq L_2$.
       Prove que $L_1^*\subseteq L_2^*$.

 \item Construa gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, \mbox{ $w$ n\~ao cont\'em a subpalavra 
              $\verb+a+\verb+b+$}\}$
        \item $\{\verb+a+^n\verb+b+^n\verb+c+^k\,\,|\,\, 0\leq n<k\}$
       \end{list}
       Para a gram\'atica do item (a), quantos passos s\~ao necess\'arios para gerar uma palavra de
       tamanho $n$?

 \item Construa AFD's para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+01+\}^*\{\verb+10+\}^*$
        \item $\{a^kb^n\,\,|\,\, k+n\geq 2\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,|w|\leq 1 \mbox{ ou o pen\'ultimo s\'{\i}mbolo de $w$
               \'e \verb+0+}\}$
        \end{list}

\item Seja um AFD $M=(E,\Sigma,\delta,i,F)$. Um {\em aut\^omato reduzido\/} correspondente a $M$ \'e o AFD
      $M'=(E',\Sigma,\delta',i',F')$, onde:
      \begin{itemize}
       \item $E'=\{[e]\,\,|\,\, e\in E\}$;
       \item $\delta'([e],a)=[\delta(e,a)]$ para todo $(e,a)\in E\times\Sigma$;
       \item $i'=[i]$; e
       \item $F'=\{[e]\,\,|\,\, e\in F\}$.
      \end{itemize}
      Prove que $\hat{\delta'}([e],w)=[\hat{\delta}(e,w)]$ para todo $e\in E$ e $w\in\Sigma^*$.
\end{enumerate}

\end{document}
 
