\documentclass[12pt, a4paper]{report}

 \addtolength{\topmargin}{-0.5in}
\addtolength{\textheight}{1.0in}

\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2002
 
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG
 
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill Entrega: 28/11/02

\begin{enumerate}
 \item Quantas palavras de tamanho $n$ existem sobre um certo alfabeto
       $\Sigma$? Quantos prefixos, sufixos e subpalavras tem uma palavra
       de tamanho $n$?

 \item Descreva mais formalmente (usando conjuntos, concatena\c c\~ao, fecho de
       Kleene, etc.) as seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] O conjunto das palavras com tr\^es \verb+0+'s.
        \item[(b)] O conjunto das palavras com, no m\'aximo, tr\^es \verb+0+'s.
        \item[(c)] O conjunto das palavras de tamanho \'{\i}mpar.
        \item[(d)] O conjunto das palavras que cont\^em \verb+01+.
        \item[(e)] O conjunto das palavras que n\~ao cont\^em \verb+01+.
        \item[(f)] O conjunto das palavras de tamanho par que cont\^em pelo
                   menos um 0.
        \item[(g)] O conjunto das palavras com n\'umero par de 0's ou \'{\i}mpar de
                   1's (ou ambos).
       \end{enumerate}

 \item D\^e defini\c c\~oes recursivas para as seguintes linguagens:
       \begin{enumerate}
        \item[(a)] $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, |w| \mbox{ \'e \'{\i}mpar}\}$
        \item[(b)] $\{0^n1^n\,\,|\,\, n\in\mbox{\bf N}\}$
        \item[(c)] $\{0^{n^2}\,|\, n\geq 0\}$.
       \end{enumerate}

 \item Que linguagens s\~ao geradas pelas gram\'aticas a seguir? N\~ao \'e preciso
       provar.
       \begin{enumerate}
        \item[(a)] $G_1=(\{X,A,B\},\{\verb+0+,\verb+1+\},R_1,X)$.
                   \begin{enumerate}
                    \item[$R_1$:] $X\,\,\rightarrow\,\, A B$
                    \item[\ ]   $A\,\,\rightarrow\,\,\verb+0+A\,\,|\,\, \lambda$
                    \item[\ ]   $B\,\,\rightarrow\,\,\verb+1+B\,\,|\,\, \verb+1+$
                   \end{enumerate}
        \item[(b)] $G_2=(\{P,I\},\{\verb+0+,\verb+1+\},R_2,P)$.
                   \begin{enumerate}
                    \item[$R_2$:] $P\,\,\rightarrow\,\,\verb+0+ P \,\,|\,\, \verb+1+I\,\,|\,\,\lambda$
                    \item[\ ]   $I\,\,\rightarrow\,\,\verb+0+ I\,\,|\,\, \verb+1+ P$
                   \end{enumerate}
        \item[(c)] $G_3=(\{P,X\},\{\verb+0+,\verb+1+\},R_3,P)$.
                   \begin{enumerate}
                    \item[$R_3$:] $P\,\,\rightarrow\,\,\verb+0+ P \verb+0+\,\,|\,\, \verb+1+X$
                    \item[\ ]   $X\,\,\rightarrow\,\,\verb+1+ X\verb+1+\,\,|\,\, \lambda$
                   \end{enumerate}
       \end{enumerate}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{enumerate}
        \item[(a)] $\{w\in\{a\}^*\,\,|\,\, |w| \,\,\mbox{\em mod}\,\, 4=0\}$
        \item[(b)] $\{w\in\{a\}^*\,\,|\,\, |w| \,\,\mbox{\em mod}\,\, 4>0\}$.
        \item[(c)] $\{a^mb^n\,\,|\,\, m\geq n\}$.
        \item[(d)] $\{ww^R\,\,|\,\, w\in\{a,b\}^*\}$.
       \end{enumerate}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para:
       \begin{enumerate}
        \item[(a)] $\{\verb+01+\}^*$.
        \item[(b)] O conjunto das palavras sobre $\{0,1\}$ com n\'umero \'{\i}mpar
                   de \verb+1+'s e terminadas em 1.
        \item[(c)] $\{\verb+a+^k\verb+b+^n\,\,|\,\, k+n\geq 3\}$.
        \item[(d)] $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em aabb}\}$.
        \item[(e)] $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w \mbox{ n\~ao termina com aabb}\}$.
        \item[(f)] $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w \mbox{ tem n\'umero
                    \'{\i}mpar de } \verb+ab+\mbox{'s}\}$.
        \item[(g)] $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, n_{\verb+1+}(w)
                    \,\,\mbox{\em mod}\,\, 3=1\}$, onde
                   $n_s(w)$ \'e a quantidade do s\'{\i}mbolo $s$ na palavra $w$.
        \item[(h)] $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,n_{\verb+0+}(w)\,\,
                    \mbox{\em mod}\,\, 3=1
                    \mbox{ e } n_{\verb+1+}(w)\,\,\mbox{\em mod}\,\, 3=2\}$.
       \end{enumerate}

 \item Sejam os seguintes AFD's:
       \begin{enumerate}
        \item $M_1=(\{p,i\},\{\verb+0+,\verb+1+\},\delta_1,p,\{p\})$, onde $\delta_1$
              \'e dada por:

              \begin{tabular}{c|cc}
               $\delta_1$ & \verb+0+ & \verb+1+ \\ \hline
                  $p$ & $i$ & $p$ \\
                  $i$ & $p$ & $i$
              \end{tabular}
        \item $M_2=(\{p,i\},\{\verb+0+,\verb+1+\},\delta_2,p,\{i\})$, onde $\delta_2$
              \'e dada por:

              \begin{tabular}{c|cc}
               $\delta_2$ & \verb+0+ & \verb+1+ \\ \hline
                  $p$ & $i$ & $i$ \\
                  $i$ & $p$ & $p$
              \end{tabular}
       \end{enumerate}
       \begin{enumerate}
        \item[(a)] Que linguagens s\~ao $L(M_1)$ e $L(M_2)$?
        \item[(b)] Utilizando as t\'ecnicas do Teorema 4, da Se\c c\~ao 2.2.3, obtenha
                   um AFD que reconhe\c ca $L(M_1)-L(M_2)$, ou seja,
                   $L(M_1)\cap\overline{L(M_2)}$.
       \end{enumerate}

 \item Para um n\'umero $n$ espec\'{\i}fico, como fazer um trecho de AFD para
       reconhecer a subpalavra $x^n$? (Suponha que a palavra $x$ tem $k$
       s\'{\i}mbolos: $x=a_1a_2\ldots a_k$.)

 \item Explique: {\em Se um AFD $M$ reconhece uma palavra de tamanho igual ao
       n\'u\-me\-ro de estados de $M$, ent\~ao $L(M)$ \'e infinita\/}.

 \item Mostre que n\~ao existe AFD que reconhece $\{x\verb+2+y\,\,|\,\,
                    x,y\in\{\verb+0+,\verb+1+\}^* \mbox{ e } |x|=|y|\}$.

\end{enumerate}

\end{document}
