\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}

\newcounter{conta}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill
          {\bf Entrega: antes do início da prova em 03/04/2012}

\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},{\tt 1}\}^+$.
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*\{{\tt 0}\}$.
        \item $\{{\tt 0}^{n}{\tt 1}^{3n}\,|\, n\in\mbox{\bf N}\}$.
        \item $\{ww^R \,|\, w\in\{{\tt 0},{\tt 1}\}^*\}$.
        \item $\{x_1+\cdots+x_n \,|\, n\geq 1 \mbox{ e } x_i\in\{{\tt 0},{\tt 1}\}^+\mbox{ para } i=1,\ldots,n\}$.
              \emph{Dica}: Faça duas definições recursivas separadas, a primeira definindo o que pode ser cada $x_i$.
       \end{list}

 \item Perguntinhas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que palavras tem cada uma das linguagens a seguir?
              \begin{quote}
               $\emptyset^*$; $\emptyset^+$;
               $\{\lambda\}^*$; $\{\lambda\}^+$;
               $\{{\tt 0}\}^*$; $\{{\tt 0}\}^+$;$\{\lambda,{\tt 0}\}^*$; $\{\lambda,{\tt 0}\}^+$.
              \end{quote}
        \item Em que situa\c{c}\~oes $L^*$ e $L^+$ são finitas?
        \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}\}$. Apresente uma condição necessária e suficiente para que uma palavra de
              $\Sigma^*$ pertença a $AA$, $AB$, $BB$, $A\cap B$, $A-B$ e $B-A$.
       \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 O conjunto das palavras de prefixo {\tt 01}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 01} como sufixo.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 01} como subpalavra.
        \item O subconjunto das palavras de $\{{\tt 0}\}^*\{{\tt 1}\}^*$ com n\'umero par de
              {\tt 0}s.
        \item O conjunto das palavras com no m\'aximo vinte s\'{\i}mbolos.
        \item O conjunto das palavras que cont\^em pelo menos um {\tt 0} e um {\tt 1}.
        \item O conjunto das palavras em que todo {\tt 0} \'e seguido de pelo menos dois
              s\'{\i}mbolos.
        \item O conjunto das palavras que cont\^em pelo menos um {\tt 00}, mas nenhum {\tt 11}.
       \end{list}
\pagebreak
 \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} P \,|\, X {\tt b} \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt a} P$
              \end{enumerate}

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

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

        \item $G_4=(\{A,X\},\{{\tt 0},{\tt 1}\},R_4,A)$.
              \begin{enumerate}
               \item[$R_4$:]  $A\,\rightarrow\, X A X \,|\, X$
               \item[\ ]      $X\,\rightarrow\,{\tt 0} X {\tt 0} \,|\, {\tt 1} X {\tt 1} \,|\, {\tt 0} \,|\, {\tt 1}$
              \end{enumerate}

        \item $G_5=(\{X,B\},\{{\tt a},{\tt b},{\tt c}\},R_5,X)$.
              \begin{enumerate}
               \item[$R_5$:] $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 linguagens da questão 1.

 \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 primeiro e o pen\'ultimo s\'{\i}mbolos
              de $w$ são {\tt 1}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o \'ultimo s\'{\i}mbolo de $w$ \'e diferente do 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 $\{x{\tt 1}{\tt 0}^n \,|\,n\geq 0, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e $x$ tem número par de {\tt 0}s}\}$.
       \end{list}

 \item Fa\c ca AFDs que reconhe\c cam: $X=\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*$. e $Y=\{{\tt 0},{\tt 1}\}^*{\{\tt 1}\}$.
       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 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}
