\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 2004
 
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG
 
\noindent {\bf Segunda Lista de Exerc\'{\i}cios} \hfill Entrega: 20/05/2004

\begin{enumerate}

 \item Construa AFN's para as seguintes linguagens, com o {\em menor n\'umero de estados
       e de transi\c c\~oes\/} que conseguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de $\{\verb+0+,\verb+1+\}^*$ em que existem pelo menos
              duas ocorr\^encias de \verb+01+ com um n\'umero par de s\'{\i}mbolos
              entre elas.
        \item $\{x{\tt 1}y\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, n_{\verb+1+}(x) \mbox{ mod } 3 = 0
               \mbox{ e } \eta(y) \mbox{ mod } 3=1\}$, onde $n_{\verb+1+}(x)$ \'e o n\'umero de
               \verb+1+'s em $X$ e $\eta(y)$ \'e o n\'umero representado por $y$ na base 2.
        \item O conjunto das palavras de $\{\verb+a+,\verb+b+,\verb+c+\}^*$
              em que o \'ultimo s\'{\i}mbolo \'e id\^entico ao primeiro.
        \item O conjunto das palavras de $\{\verb+a+,\verb+b+,\verb+c+\}^*$
              em que o \'ultimo s\'{\i}mbolo \'e diferente do primeiro.
        \item O conjunto das palavras de $\{\verb+a+,\verb+b+,\verb+c+\}^*$
              em que o \'ultimo s\'{\i}mbolo n\~ao tenha ocorrido antes. (Use v\'arios estados
              iniciais.)
       \end{list}
 
 \item Obtenha um AFD equivalente ao AFN do item (a) da quest\~ao anterior, usando o
       m\'etodo visto em aula.

 \item Seja o AFN$\lambda$ $M=(\{0,1,2,3,4\},\{\verb+a+,\verb+b+,\verb+c+\},\delta,\{0\},\{3,4\})$,
       onde $\delta$ \'e dada por:
       \begin{center}
        \begin{tabular}{c|cccc}
         $\delta$ & \verb+a+ & \verb+b+ & \verb+c+ & $\lambda$\\ \hline
              $0$ & $\{1\}$  & $\{1\}$  & $\{\}$   & $\{2\}$ \\
              $1$ & $\{0\}$  & $\{0\}$  & $\{\}$   & $\{\}$ \\
              $2$ & $\{2\}$  & $\{2\}$  & $\{2,3\}$ & $\{\}$ \\
              $3$ & $\{4\}$  & $\{4\}$  & $\{4\}$ & $\{\}$ \\
              $4$ & $\{\}$  & $\{\}$  & $\{\}$ & $\{\}$ \\
        \end{tabular}
       \end{center}
       \begin{enumerate}
        \item[(a)] Construa um AFN equivalente.
        \item[(b)] A partir do AFN construa uma express\~ao regular que denote a linguagem
                   reconhecida.
       \end{enumerate}

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares, utilizando o lema
       do bombeamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{x{\tt 1}y\in\{{\tt 0},{\tt 1}\}^*\,\,|\,\, |x|=|y|\}$
        \item $\{\verb+0+^ny\,\,|\,\, n\geq 0 \mbox{ e } |y|\leq n\}$
        \item $\{\verb+0+^{n^2}\,\,|\,\, n\geq0\}$
       \end{list}

 \item Prove que os seguintes conjuntos s\~ao ou n\~ao s\~ao linguagens regulares.
       Procure usar as propriedades de fechamento.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\overline{\{\verb+a+\}^*\{\verb+b+\}^*}$
        \item $\{xy \,\,|\,\, x,y\in\{\verb+a+,\verb+b+\}^* \mbox{ e } |x|=|y|
                \mbox{ e } n_{\verb+a+}(x)=n_{\verb+b+}(y)\}$
        \item $\{xy \,\,|\,\, x,y\in\{\verb+a+,\verb+b+\}^* \mbox{ e } |x|=|y|
                \mbox{ e } n_{\verb+a+}(x)\not=n_{\verb+b+}(y)\}$
       \end{list}

 \item Mostre que a classe das linguagens regulares \'e fechada sob as seguintes
       opera\c c\~oes (suponha que o alfabeto de $L$ \'e $\Sigma$):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pf\/}(L)=\{x \,\,|\,\, xy\in L$ para algum $y\in\Sigma^*\}$.
        \item $\mbox{\em sf\/}(L)=\{z \,\,|\,\, yz\in L$ para algum $y\in\Sigma^*\}$.
        \item $\mbox{\em sp\/}(L)=\{y \,\,|\,\, xyz\in L$ para algum $x,z\in\Sigma^*\}$.
       \end{list}

 \item Seja $L$ uma linguagem {\bf n\~ao} regular e $R$ uma regular. Mostre que sim ou que
       n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L\cup R$ \'e uma linguagem n\~ao regular.
        \item $L\cap R$ \'e uma linguagem n\~ao regular.
        \item $LR$ \'e uma linguagem n\~ao regular.
       \end{list}

 \item Sejam $L_1$ e $L_2$ duas linguagens {\bf n\~ao} regulares. Mostre que sim ou que
       n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1\cup L_2$ \'e uma linguagem n\~ao regular.
        \item $L_1L_2$ \'e uma linguagem n\~ao regular.
        \item $L_1^*$ \'e uma linguagem n\~ao regular.
        \item $\{w \,\,|\,\, w $ \'e uma subpalavra de $L_1\}$ \'e uma linguagem
              n\~ao regular.
       \end{list}

 \item Encontre ER's e GR's para os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, |w|\in \{0,2,3\}\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\,$ \verb+b+'s s\'o podem ocorrer nas
              posi\c c\~oes \'{\i}mpares de $w\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ cont\'em exatamente um \verb+abb+$\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ n\~ao cont\'em \verb+abb+$\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ cont\'em \verb+a+ e $|w|$ \'e
               m\'ultiplo de 3$\}$
       \end{list}

 \item Obtenha ER's que denotem as linguagens sobre $\{\verb+0+,\verb+1+\}$ abaixo, a partir
       de AFN's que reconhe\c cam as mesmas.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras em que as posi\c c\~oes pares s\'o cont\^em \verb+0+'s
              e as \'{\i}mpares s\'o cont\^em \verb+1+'s.
        \item O conjunto das palavras que n\~ao cont\'em a subpalavra \verb+111+.
        \item O conjunto das palavras com n\'umero \'{\i}mpar de \verb+0+'s e \'{\i}mpar de
              \verb+1+'s.
       \end{list}

\end{enumerate}

\end{document}
