\documentclass[11pt, a4paper]{report}

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

\newcounter{conta}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill
          {\bf Entrega: 31/08/2010}

\vspace*{3mm}
\begin{enumerate}
 \item Fa\c ca defini\c c\~oes recursivas das seguintes linguagens, considerando a
       \textit{concatena\c{c}\~ao\/} como a opera\c{c}\~ao b\'asica no passo recursivo:\footnote{Veja a
       Se\c{c}\~ao 1.7, p\'ag. 28, do livro-texto.}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^{3n}{\tt 1}^{3n}\,|\, n\in\mbox{\bf N}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ \'e pal\'{\i}ndromo}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ cont\'em } {\tt 01}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ come\c{c}a com {\tt 0} e termina com {\tt 1}}\}$.
        \item $\{x{\tt 01}y \,|\, x,y\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|=|y|\}$.
       \end{list}

 \item Perguntinhas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que palavras tem cada uma das linguagens a seguir?
              \begin{quote}
               $\emptyset$; $\emptyset^*$; $\emptyset^+$;
               $\{\lambda\}$; $\{\lambda\}^*$; $\{\lambda\}^+$;
               $\{{\tt 0}\}$; $\{{\tt 0}\}^*$; $\{{\tt 0}\}^+$;$\{\lambda,{\tt 0}\}^*$; $\{\lambda,{\tt 0}\}^+$.
              \end{quote}
        \item Em que situa\c{c}\~oes $L^*$ \'e infinita?
        \item Seja $\Sigma$ um alfabeto. Explique que palavras pertencem a cada uma das linguagens:
              \begin{itemize}
               \item $\Sigma^n$ para cada $n\geq 0$; que valor tem $|\Sigma^n|$?
               \item $(\Sigma\cup\{\lambda\})^n$ para cada $n\geq 0$; que valor tem $|(\Sigma\cup\{\lambda\})^n|$?
              \end{itemize}
        \item Sejam $\Sigma=\{{\tt a},{\tt b}\}$,  $A=\{{\tt a}\}\Sigma^*$ e
              $B=\Sigma^+\{{\tt b}\}$. Descreva $AA$, $A\cap B$ e $A-B$.
       \end{list}

 \item Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas \textit{conjuntos finitos} e opera\c{c}\~oes de \textit{uni\~ao}, \textit{interse\c{c}\~ao},
       \textit{complementa\c{c}\~ao}, \textit{concatena\c c\~ao} e \textit{fecho de Kleene}. Procure obter uma
       descri\c c\~ao bem concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \,|\, |w|=4 \mbox{ e } w \mbox{ n\~ao cont\'em a subpalavra } {\tt 01}\}$.
        \item O conjunto das palavras que cont\^em {\tt 01}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 01}.
        \item O subconjunto das palavras de $\{{\tt 0}\}^*\{{\tt 1}\}^*$ com n\'umero \'{\i}mpar de
              {\tt 0}s e par de {\tt 1}s.
        \item O conjunto das palavras iniciadas com {\tt 00} com no m\'aximo vinte s\'{\i}mbolos.
        \item O conjunto das palavras com dois a vinte s\'{\i}mbolos.
        \item O conjunto das palavras que cont\^em {\tt 00} ou {\tt 11} ou ambas.
        \item O conjunto das palavras que cont\^em {\tt 00}, mas n\~ao {\tt 11}.
        \item O conjunto das palavras em que todo {\tt 0}  \'e seguido de pelo menos dois
              s\'{\i}mbolos.
       \end{list}

 \item Identifique as linguagens que s\~ao geradas pelas gram\'aticas a seguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_1=(\{P,X\},\{{\tt a},{\tt b}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt a} X \,|\, {\tt b} P \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt b} P$
              \end{enumerate}

        \item $G_2=(\{P,A\},\{{\tt 0},{\tt 1}\},R_2,P)$.
              \begin{enumerate}
               \item[$R_2$:]  $P\,\rightarrow\,{\tt a}P{\tt a}\,|\, A$
               \item[\ ]      $A\,\rightarrow\,{\tt b}A \,|\, {\tt b}$
              \end{enumerate}

        \item $G_3=(\{A,X\},\{{\tt 0},{\tt 1}\},R_3,A)$.
              \begin{enumerate}
               \item[$R_3$:]  $A\,\rightarrow\, X A \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt 0} X {\tt 1} \,|\, {\tt 01}$
              \end{enumerate}

        \item $G_4=(\{X,B\},\{{\tt a},{\tt b},{\tt c}\},R_4,X)$.
              \begin{enumerate}
               \item[$R_4$:] $X\,\rightarrow\,{\tt a}BX \,|\,{\tt abc}$ 
               \item[\ ]  $B{\tt a}\,\rightarrow\,{\tt a}B$
               \item[\ ]  $B{\tt b}\,\rightarrow\,{\tt b}B$
               \item[\ ]  $B{\tt c}\,\rightarrow\,{\tt b}{\tt cc}$
              \end{enumerate}
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 0}\}^*\{{\tt 1}\}^*$.
        \item $\{{\tt 0}\}^*\{{\tt 1}\}^*\{{\tt 0}\}^*$.
        \item $\{\lambda,{\tt 0}\}\{{\tt 11}\}^*\{\lambda,{\tt 0}\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, \mbox{ o n\'umero de {\tt a}'s em
                   $w$ \'e par}\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt ab} nem
                   {\tt bc}}\}$.
        \item $\{{\tt a}^m{\tt b}^{m+n+1}{\tt c}^n\,|\, m,n\geq 0\}$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFDs) que reconhe\c cam
       as linguagens da quest\~ao 3. Apresente apenas os diagramas de estados.

 \item Construa AFDs que reconhe\c cam
       as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w|\geq 2 \mbox{ e o pen\'ultimo s\'{\i}mbolo
              de $w$ \'e {\tt 1}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o \'ultimo s\'{\i}mbolo
              de $w$ \'e igual ao primeiro}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ os tr\^es \'ultimos s\'{\i}mbolos
                 de $w$ n\~ao s\~ao {\tt 000}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ em $w$ o s\'{\i}mbolo da
               posi\c{c}\~ao $2i$ \'e diferente daquele na posi\c{c}\~ao $2i+2$
               para cada $i\geq 1\}$.
       \end{list}

 \item Fa\c ca AFDs 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 00}$\}$. Bastam apenas os diagramas
       de estados. Em seguida, obtenha o produto dos dois AFDs e explicite
       que estados finais ele deve ter para reconhecer:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X\cap Y$.
        \item $X\cup Y$.
        \item $X-Y$.
       \end{list}

 \item Explique porque para um estado $e$ e uma palavra $x$, se $\hat{\delta}(e,x)=e$,
       ent\~ao $\hat{\delta}(e,x^n)=e$ para todo $n\geq 0$.

 \item Explique porque se um AFD $M$ reconhece uma palavra de tamanho maior ou igual ao n\'umero de
       estados de $M$, ent\~ao $L(M)$ \'e infinita.
\end{enumerate}

\end{document}
