\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2016 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Lista de Exercícios} \\
\noindent \emph{Data de entrega}: até 16:40h de 07/04/2016. Local: sala 7328 ou em sala de aula.

\vspace*{3mm}
\begin{enumerate}
 \item Sejam $A=\{\tt{00},{\tt 11}\}$, $B=\{\tt{01},{\tt 10}\}$ e $C=\{\lambda,{\tt 1}\}$. Calcule:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $AA$;
        \item $AC$;
        \item $CCC$;
        \item $ABC$;
        \item $A(B\cup C)$.
       \end{list}

 \item Sejam $\Sigma=\{\tt{0},{\tt 1}\}$, $A=\Sigma^*\{\tt{0}\}$ e $B=\{{\tt 1}\}\Sigma^*$. Descreva, em português, as
       linguagens a seguir. Não é necessário dizer que as palavras são de {\tt 0}s e {\tt 1}s. Por exemplo, $A$ é o ``conjunto
			 das palavras que terminam com {\tt 0}''.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $A\cup B$;
        \item $A\cap B$;
        \item $A-B$;
        \item $AB$.
       \end{list}

 \item Perguntinhas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Em que situações $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 \label{x} Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas \textit{conjuntos finitos} e operações de \textit{união}, \textit{interseção},
       \textit{complementação}, \textit{concatenação} e \textit{fecho de Kleene}. Procure obter uma
       descrição bem concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de prefixo {\tt 01}.
        \item O conjunto das palavras com número par de {\tt 0}s.
        \item O conjunto das palavras de $\{{\tt 0}\}^*\{{\tt 1}\}^*$ com número par de {\tt 0}s.
        \item O conjunto das palavras com cinco símbolos.
        \item O conjunto das palavras com no mínimo cinco símbolos.
        \item O conjunto das palavras com no máximo cinco símbolos.
        \item O conjunto das palavras que contêm pelo menos um {\tt 0} e um {\tt 1}.
        \item O conjunto das palavras que contêm pelo menos um {\tt 00}, mas nenhum {\tt 11}.
        \item O conjunto das palavras que não contêm {\tt 01} como sufixo.
       \end{list}

 \item Identifique as linguagens que são geradas pelas gramáticas a seguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_0=(\{X,Y\},\{{\tt 0},{\tt 1}\},R_0,X)$.
              \begin{enumerate}
               \item[$R_0$:]  $X\,\rightarrow\,{\tt 0} X \,|\, Y$
               \item[\ ]      $Y\,\rightarrow\,{\tt 1} Y \,|\, {\tt 1}$
              \end{enumerate}

        \item $G_1=(\{P\},\{{\tt a},{\tt b}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt a} P {\tt a} \,|\, {\tt b} P {\tt b} \,|\, \lambda$
              \end{enumerate}

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

        \item $G_3=(\{P,X\},\{{\tt a},{\tt b}\},R_3,P)$.
              \begin{enumerate}
               \item[$R_3$:]  $P\,\rightarrow\,{\tt a} P \,|\, X {\tt b} \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt a} P$
              \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áticas para as linguagens:
       \begin{list}{(\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}\}^*\}$.
       \end{list}

 \item  Faça um diagrama de estados, similar àquele do quebra-cabeça leão-raposa-repolho para o problema dos missionários 
				 e canibais:
         \begin{quote}
           Três missionários e três canibais devem atravessar um rio. Para isso, dispõem de uma canoa que pode transportar
					 no máximo duas pessoas de cada vez. Durante a travessia, se o número de canibais for maior que o de missionários
					 em qualquer uma das margens, os canibais comem os missionários. Determinar um plano para travessia em que nenhum
					 missionário seja devorado.
         \end{quote}

 \item Faça um diagrama de estados para uma máquina que determine se uma sequência ternária (com dígitos 0, 1 e 2) é divisível
       por 4.
 \item Construa autômatos finitos determinísticos (AFDs) que reconheçam as linguagens da questão \ref{x}. Apresente apenas os 
       diagramas de estados.

 \item Construa AFDs que reconheçam  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último símbolos de $w$ são {\tt 1}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o último símbolo de $w$ é diferente do primeiro}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ os três últimos símbolos de $w$ não são {\tt 000}}\}$.
        \item O conjunto das palavras em que todo {\tt 0} é seguido de pelo menos dois símbolos.
 %       \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ça AFDs que reconheçam: $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úmero de
       estados de $M$, então $L(M)$ é infinita.

 \item Construa AFNs para as seguintes linguagens, com o {\em menor número de estados e de transições} que conseguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$, de dois ou mais símbolos, em que o último símbolo
              seja diferente do primeiro.
        \item O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$ em que o último símbolo tenha ocorrido antes no 
				      mínimo uma vez.
        \item O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$ em que o último símbolo tenha ocorrido antes no 
				      máximo duas vezes.
        \item $\{x{\tt 1}y\in\{{\tt 0},{\tt 1}\}^*\,|\, |x| \,\mbox{\em mod\/}\, 3 = 1
               \mbox{ e } \eta(y) \,\mbox{\em mod\/}\, 3 = 1\}$, sendo $\eta(y)$ o número representado por $y$ na base 2. 
       \end{list}
 
 \item Seja o AFN com o diagrama de estados a seguir:

       \begin{picture}(120,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](1)(20,30){1}
        \node(2)(40,30){2}
        \node[Nmarks=i, iangle=180](3)(40,10){3}
        \node[Nmarks=r](4)(60,10){4}

        \drawedge[curvedepth=4](1,2){{\tt 0}}
        \drawedge[curvedepth=4](2,1){{\tt 0}}
        \drawedge[curvedepth=0](2,3){{\tt 0}}
        \drawedge[curvedepth=4](3,4){{\tt 1}}
        \drawedge[curvedepth=4](4,3){{\tt 1}}
        \drawloop[loopangle=90](1){{\tt 1}}
        \drawloop[loopangle=270](3){{\tt 0}}
        \drawloop[loopangle=270](4){{\tt 0}}
       \end{picture}

       Construa um AFD equivalente usando o método visto em aula (\textit{subset construction}).

\item Seja o AFN$\lambda$ $M$:

       \begin{picture}(120,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](A)(20,30){A}
        \node(B)(40,30){B}
        \node(C)(20,10){C}
        \node[Nmarks=r](D)(40,10){D}
        \node[Nmarks=r](E)(60,10){E}

        \drawedge[curvedepth=0](A,B){$\lambda$}
        \drawedge[curvedepth=0](B,D){$\lambda$}
        \drawedge[curvedepth=0](A,C){$\lambda$}
        \drawedge[curvedepth=0](C,D){$\lambda$}
        \drawedge[curvedepth=0](D,E){$\lambda$}
        \drawloop[loopangle=90](A){{\tt a}}
        \drawloop[loopangle=0](B){{\tt b}}
        \drawloop[loopangle=180](C){{\tt c}}
        \drawloop[loopangle=270](D){{\tt d}}
        \drawloop[loopangle=270](E){{\tt a}}
       \end{picture}

       Construa um AFN $N$, equivalente a $M$, usando o método visto  em aula.
\end{enumerate}

\end{document}
