\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\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 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Primeira Lista de Exerc\'{\i}cios}

\vspace*{3mm}
\noindent \underline{Observa\c{c}\~{a}o}: Os n\'{u}meros dos exerc\'{\i}cios extra\'{\i}dos de livros
indicados no Plano de Curso est\~{a}o apresentados seguidos das iniciais dos autores
concatenadas com os dois \'{u}ltimos d\'{\i}gitos do ano da publica\c{c}\~{a}o do livro.

\section{Preliminares Matem\'{a}ticas}
 
\begin{enumerate}
 \item Prove:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$.
        \item $\overline{(A\cup B)}=(\overline{A}\cap\overline{B})$.
        \item se $A\cap B=A\cup B$, ent\~{a}o $A=B$.
       \end{list}
 \item (0.3.7 de K95) Prove que sim ou que n\~{a}o ($\mbox{\cal P}(X)$ \'{e} o conjunto
       pot\^{e}ncia de $X$):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\cal P}(A)\cap\mbox{\cal P}(B)=\mbox{\cal P}(A\cap B)$?
        \item $\mbox{\cal P}(A)\cup\mbox{\cal P}(B)=\mbox{\cal P}(A\cup B)$?
       \end{list}
 \item Que condi\c{c}\~{a}o deve ser satisfeita por duas fun\c{c}\~{o}es $f$ e $g$ para que
       $f\cup g$ seja uma fun\c{c}\~{a}o?
 \item Sejam $A$ e $B$ conjuntos de $n$ e $k$ elementos, respectivamente.
       Determine quantas fun\c{c}\~{o}es de $A$ para $B$ existem de cada um dos
       tipos: (a) totais; (b) parciais; (c) injetivas; (d) sobrejetivas; e (e)
       bijetivas.
 \item (11, cap. 1 de S88) Uma fun\c{c}\~{a}o total $f:\mbox{\bf N}\rightarrow
       \mbox{\bf N}$ \'{e} dita ser {\em monot\^{o}nica crescente\/} se $f(n)<f(n+1)$
       para todo $n\in\mbox{\bf N}$. Prove que existe um n\'{u}mero n\~{a}o cont\'{a}vel de
       fun\c{c}\~{o}es monot\^{o}nicas crescentes.
 \item (19, cap. 1 de S88) D\^{e} uma defini\c{c}\~{a}o recursiva do conjunto dos
       subconjuntos finitos de {\bf N}. Use uni\~{a}o como operador.
 \item (25, cap. 1 de S88) D\^{e} uma defini\c{c}\~{a}o recursiva do conjunto dos nodos
       de um grafo direcionado que podem ser alcan\c{c}ados a partir de um nodo
       $x$. Use a rela\c{c}\~{a}o de adjac\^{e}ncia como opera\c{c}\~{a}o.
 \item Seja uma \'{a}rvore em que cada nodo tem no m\'{a}ximo $k$ filhos. Se ela tiver
       exatamente $i$ nodos internos, quais s\~{a}o os n\'{u}meros m\'{\i}nimo e m\'{a}ximo de
       nodos que a fronteira da mesma pode ter? 
 \item (21, cap. 1 de S88) Prove, por indu\c{c}\~{a}o, que
       $\sum_{i=0}^{n}2^i=2^{n+1}-1$ para todo $n\in {\mbox N}$.
 \item (29, cap. 1 de S88) Uma {\em \'{a}rvore bin\'{a}ria completa\/} de profundidade
       $n$ \'{e} uma \'{a}rvore estritamente bin\'{a}ria na qual cada nodo nos n\'{\i}veis
       anteriores a $n$ tem filhos e cada nodo no n\'{\i}vel $n$ \'{e} uma folha. Prove
       que uma \'{a}rvore bin\'{a}ria completa de profundidade $n$ tem $2^{n+1}-1$
       nodos.
\end{enumerate}

\section{Linguagens}

\begin{enumerate}
 \item (4, cap. 2 de S88) Prove que $(w^R)^i=(w^i)^R$ para todo {\em string\/}
       $w$ e todo $i\geq 0$.
 \item (1.3.3 de K95) Quais s\~{a}o os {\em strings\/} em $\{\lambda,a\}^n$, para
       um certo $n$ arbitr\'{a}rio?
 \item (0.2.2 de AU72) Prove que sim ou que n\~{a}o: $L^+=L^*-\{\lambda\}$.
 \item (0.2.6 de AU72) Pode $L^*$ ou $L^+$ ser $\phi$? Sob quais circunst\^{a}ncias
       $L^*$ \'{e} finito? E $L^+$?
 \item (10, 13, 19, 20, 22, 23, cap. 2 de S88) D\^{e} express\~{o}es regulares que
       denotem os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ que n\~{a}o cont\^{e}m
              $aa$.
        \item o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ nos quais cada
              $b$ \'{e} seguido por pelo menos um $c$.
        \item o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais o n\'{u}mero
              $a$'s \'{e} divis\'{\i}vel por 3.
        \item o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada $a$
              \'{e} precedido (imediatamente) ou seguido (imediatamente) por $b$.
        \item o conjunto dos {\em strings\/} sobre $\{a,b\}$ com n\'{u}mero par de
              $a$'s e n\'{u}mero par de $b$'s.
        \item o conjunto dos {\em strings\/} de tamanho \'{\i}mpar sobre $\{a,b\}$
              que cont\^{e}m exatamente dois $b$'s.
       \end{list}
 \item (2.11 de HU79) Descreva, em portugu\^{e}s, os conjuntos denotados pelas
       seguintes express\~{o}es regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\boldmath $(11\cup 0)^*(00\cup 1)^*$}
        \item {\boldmath $(1\cup 01\cup 001)^*(\lambda\cup 0\cup 00)^*$}
        \item {\boldmath $[00\cup 11\cup (01\cup 10)(00\cup 11)^*(01\cup 10)]^*$}
       \end{list}
 \item (2.2.7 e 2.2.9 de K95) Simplifique as seguintes express\~{o}es regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\boldmath $\phi^*\cup a^*\cup b^*\cup (a \cup b)^*$}
        \item {\boldmath $(aa)^*a\cup (aa)^*$}
        \item {\boldmath $(a \cup b)^*a(a\cup b)^*$}
        \item {\boldmath $a(\lambda \cup aa)^*a \cup \lambda$}
        \item {\boldmath $(a\cup b)(\lambda \cup aa)^*(\lambda\cup aa) \cup a\cup b$}
        \item {\boldmath $a^*b((a\cup b)a^*b)^*(a\cup b)(aa)^*\cup a(aa)^*\cup
               a^*b((a\cup b)a^*b)^*$}
       \end{list}
\end{enumerate}
 
\end{document}
\endinput
\end
 
