\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 Lista de Exerc\'{\i}cios} \hfill Data de entrega: 05/09/2000


\section{Conceitos Preliminares}

\begin{enumerate}
 \item Mostre que s\~ao v\'alidas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\alpha\wedge\neg\alpha)\rightarrow\beta$
        \item $(\alpha\rightarrow\beta)\vee\alpha$
       \end{list}
 \item Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\alpha\vee\beta)\rightarrow\gamma\equiv
              (\alpha\rightarrow\gamma)\wedge(\beta\rightarrow\gamma)$
        \item $\alpha\rightarrow\gamma\models
              (\alpha\wedge\beta)\rightarrow\gamma$
       \end{list}

 \item Prove que $(A-B)-C=A-(B\cup C)$
 \item Desenvolva um m\'etodo sistem\'atico (algoritmo) para gerar todas as parti\c c\~oes de um conjunto
       de $n$ elementos.

 \item Uma rela\c c\~ao $R$ sobre $A$ \'e dita ser {\em anti-sim\'etrica\/} se, e somente se, se $x Ry$
       e $y Rx$ ent\~ao $x=y$, para todo $x,y\in A$. Mostre que uma rela\c c\~ao $R$ sobre $A$ \'e
       anti-sim\'etrica se, e somente se, $R\cap R^{-1}\subseteq \iota_A$.
 \item Seja a rela\c c\~ao $R=\{((x_1,x_2),(y_1,y_2))\in(\mbox{\bf N}\times\mbox{\bf N})^2\,\,|\,\, x_1/x_2=y_1/y_2\}$.
         Prove que $R$ \'e uma rela\c c\~ao de equival\^encia. Quais s\~ao as classes de equival\^encia de $R$?

 \item Sejam duas fun\c c\~oes totais $f:A\rightarrow B$ e $g:B\rightarrow C$. Especifique que propriedades deve ter a
         fun\c c\~ao $g\circ f$ nos seguintes casos:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $f$ e $g$ s\~ao injetivas;
          \item $f$ e $g$ s\~ao sobrejetivas;
          \item $f$ e $g$ s\~ao bijetivas.
         \end{list}
 \item Sejam $f$ e $g$ fun\c c\~oes sobre {\bf R} tais que $f(n)=an+b$ e $g(n)=cn+d$. Se $g\circ f=f\circ g$, que
       rela\c c\~ao existir\'a entre os coeficientes $a$, $b$, $c$ e $d$?


 \item O conjunto das fun\c c\~oes de {\bf N} para $\{0,1\}$ pode ser visto como o conjunto de todos os problemas de
       decis\~ao (problemas cuja resposta \'e sim ou n\~ao).
       Prove que tal conjunto n\~ao \'e enumer\'avel.


 \item Fa\c ca uma defini\c c\~ao recursiva do n\'umero de elementos do conjunto pot\^encia de conjuntos finitos.
 \item Continuando no estilo do Exemplo 31 da apostila, fa\c ca uma defini\c c\~ao recursiva da opera\c c\~ao de
         multiplica\c c\~ao sobre {\bf N}.

 \item Prove, por indu\c c\~ao, que $\sum_{k=1}^{n}[1/k(k+1)]=n/(n+1)$ para todo n\'umero natural $n\geq 1$.
 \item Prove que o n\'umero de abre par\^enteses de qualquer prefixo de qualquer afirmativa da linguagem LP do
       Exemplo 32 da apostila \'e maior ou igual ao n\'umero de fecha par\^enteses.

 \item Prove por indu\c c\~ao que toda \'arvore bin\'aria de altura $k\geq 0$ possui, no m\'aximo:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $2^k$ folhas;
        \item $2^{k+1}-1$ v\'ertices.
       \end{list}

 \item Descreva mais formalmente as seguintes linguagens sobre o alfabeto $\{\verb+0+,\verb+1+\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item o conjunto das palavras com, no m\'{\i}nimo, um \verb+0+;
        \item o conjunto das palavras de tamanho \'{\i}mpar;
        \item o conjunto das palavras com um prefixo de um ou mais \verb+0+'s seguido (imediatamente)
              de um sufixo de zero ou mais \verb+1+'s;
        \item o conjunto dos pal\'{\i}ndromos que n\~ao contenham s\'{\i}mbolos consecutivos id\^enticos.
        \item o conjunto das palavras de tamanho par cuja primeira metade \'e id\^entica \`a segunda;
       \end{list}
       Procure ser bem preciso e conciso.
 \item Prove que $L^*=\bigcup_{n\in\mbox{\bf N}}L^n$.
       ({\em Sugest\~ao:\/} para provar que $L^*\subseteq\bigcup_{n\in\mbox{\bf N}}L^n$, use indu\c c\~ao sobre $|w|$,
       e para provar que $\bigcup_{n\in\mbox{\bf N}}L^n\subseteq L^*$, use indu\c c\~ao sobre $n$.)
 \item Prove por indu\c c\~ao que:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $L^*L^*=L^*$;
          \item $(L^*)^*=L^*$.
         \end{list}

 \item Construa gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, \mbox{ o n\'umero de \verb+a+'s em $w$ \'e par}\}$
        \item $\{\verb+a+^n\verb+b+^n\,\,|\,\, n\in{\bf N}\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w=w^R\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w=w^R$ e $w$ n\~ao cont\'em s\'{\i}mbolos consecutivos
               id\^enticos$\}$
        \item $\{\verb+a+^n\verb+b+^n\verb+c+^n\verb+d+^n\,\,|\,\, n\in{\bf N}\}$
       \end{list}
 \item Para as gram\'aticas dos itens (b) e (c) do exerc\'{\i}cio anterior, determine o n\'umero de passos necess\'ario
       para gerar uma palavra de tamanho $n$.

 \item Diz-se que um PD $P$ \'e {\em redut\'{\i}vel\/} a um PD $Q$, se existe um algoritmo ${\cal A}$ que,
       recebendo $x$ como entrada, produz um resultado ${\cal A}(x)$ tal que a resposta determinada
       por $P$ para a entrada $x$ \'e id\^entica \`a determinada por $Q$ para a entrada ${\cal A}(x)$, qualquer
       que seja a entrada $x$. Diz-se, com isto,
       que o algoritmo ${\cal A}$ pode ser usado para {\em reduzir\/} o problema $P$ ao problema $Q$.

       Seja $D$ um PD decid\'{\i}vel e $I$ um PD indecid\'{\i}vel. O que se pode dizer de um PD $X$, com rela\c c\~ao \`a
       sua decidibilidade, se:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $D$ \'e redut\'{\i}vel a $X$?
        \item $X$ \'e redut\'{\i}vel a $D$?
        \item $I$ \'e redut\'{\i}vel a $X$?
        \item $X$ \'e redut\'{\i}vel a $I$?
       \end{list}
\end{enumerate}

\section{M\'aquinas de Estado-Finito}

\begin{enumerate}
 \item Fa\c ca um diagrama de estados, similar \`aquele do problema da Se\c c\~ao 1.1.1 da apostila, para o problema
       dos mission\'arios e canibais:
         \begin{quote}
           Tr\^es mission\'arios e tr\^es canibais devem atravessar um rio. Para isto disp\~oem de uma canoa que pode
           transportar no m\'aximo 2 pessoas de cada vez. Durante a travessia, se o n\'umero de canibais ficar maior do que o
           de mission\'arios em qualquer uma das margens, os canibais comem os mission\'arios. Determinar um plano para
           travessia em que nenhum mission\'ario seja devorado.
         \end{quote}

 \item Fa\c ca um diagrama de estados, usando a id\'eia apresentada na Se\c c\~ao 1.1.2 da apostila, para uma m\'aquina que
         determine se uma seq\"u\^encia tern\'aria (com d\'{\i}gitos 0, 1  e 2) \'e divis\'{\i}vel por 4.

 \item Construa AFD's para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ cada \verb+0+ de $w$ \'e imediatamente seguido de,
              no m\'{\i}nimo, dois \verb+1+'s$\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ os primeiros 4 s\'{\i}mbolos de $w$ cont\^em,
              no m\'{\i}nimo, dois \verb+1+'s$\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ $w$ n\~ao cont\'em \verb+000+ nem \verb+111+$\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ os \'ultimos 3 s\'{\i}mbolos de $w$ \underline{n\~ao}
              s\~ao \verb+000+$\}$
        \item $\{w\in\{\verb+0+,\verb+1+,\verb+2+\}^*\,\,|\,\, w$ tem n\'umero par de \verb+0+'s, par
              de \verb+1+'s e par de \verb+2+'s$\}$
        \end{list}
\item Prove que $\hat{\delta}(e,xy)=\hat{\delta}(\hat{\delta}(e,x),y)$, onde $\delta$ \'e a fun\c c\~ao de transi\c c\~ao de
        um AFD, $e$ \'e um estado e $x$ e $y$ s\~ao palavras.
\item Minimize o AFD do Exemplo 60, Figura 1.13, da apostila..
\item Utilizando um racioc\'{\i}nio an\'alogo ao utilizado no Exemplo 62 (baseado no Teorema 5) da apostila,
        prove que n\~ao existe AFD que reconhece $\{x\verb+c+y\,\,|\,\, |x|=|y| \mbox{ e } x,y\in\{\verb+a+,\verb+b+\}^*\}$.

\end{enumerate}

\end{document}
 
