\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 Segunda Lista de Exerc\'{\i}cios} \hfill Entrega: 09/01/03

\begin{enumerate}

 \item Construa AFN's para as seguintes linguagens, com o {\em menor n\'umero de estados\/}
       que conseguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{xy\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, n_{\verb+1+}(x) \mbox{ mod } 3 = 0
               \mbox{ e } \eta(y) \mbox{ mod } 3=1\}$, onde $\eta(y)$ \'e o n\'umero
               representado por $y$ na base 2.
        \item $\{xyx\,\,|\,\, x,y\in\{\verb+a+,\verb+b+\}^* \mbox{ e } |x|=3\}$.
        \item O conjunto das palavras de $\{\verb+a+,\verb+b+,\verb+c+\}^*$
              em que o \'ultimo s\'{\i}mbolo n\~ao tenha ocorrido antes.
        \item $\{xy\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,|y|=4 \mbox{ e }
               n_{\verb+1+}(y)>n_{\verb+0+}(y)\}$.
       \end{list}

 \item Obtenha um AFD equivalente ao primeiro AFN da primeira quest\~ao, usando o
       m\'etodo visto em aula.

 \item Seja o AFN$\lambda$ $M=(\{0,1,2\},\{\verb+a+,\verb+b+,\verb+c+\},\delta,\{0\},\{2\})$,
       onde $\delta$ \'e dada por:
       \begin{center}
        \begin{tabular}{c|cccc}
         $\delta$ & \verb+a+ & \verb+b+ & \verb+c+ & $\lambda$\\ \hline
         $0$ & $\{0\}$ & $\{1\}$ & $\{\}$  & $\{\}$ \\
         $1$ & $\{\}$  & $\{\}$  & $\{2\}$ & $\{0\}$ \\
         $2$ & $\{\}$  & $\{\}$  & $\{1\}$ & $\{\}$ \\
        \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 $\{\verb+a+^{2n}\verb+b+^{2n+1}\,\,|\,\, n\geq 0\}$
        \item $\{xx \,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$
        \item $\{\verb+0+^ny\,\,|\,\, n\geq 0 \mbox{ e } |y|\leq n\}$
       \end{list}

 \item Prove que os seguintes conjuntos s\~ao ou n\~ao s\~ao linguagens regulares:
       \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)\}$
        \item Os 3 conjuntos correspondentes \`as interse\c c\~oes destes 3
              conjuntos dois a dois.
       \end{list}

 \item Mostre que a classe das linguagens regulares \'e fechada sob as seguintes
       opera\c c\~oes ($a$ \'e um certo s\'{\i}mbolo do alfabeto de $L$):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pf\/}_a(L)=\{x \,\,|\,\, xa\in L \}$
        \item $\mbox{\em sf\/}_a(L)=\{y \,\,|\,\, ay\in L \}$
       \end{list}

 \item Sejam $L_1$ e $L_2$ duas linguagens. Mostre que sim ou que n\~ao:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item se $L_1\cup L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem
                regular.
          \item se $L_1L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem
                re\-gu\-lar.
          \item se $L_1^*$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem regular.
          \item se $L_1$ \'e uma linguagem regular ent\~ao $\{w \,\,|\,\, w $ \'e uma
                subpalavra de $L_1\}$ \'e uma linguagem 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+\}^*\,\,|\,\, 1\leq |w|\leq 10\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ cont\'em \verb+a+ e $|w|$ \'e
              \'{\i}mpar$\}$
        \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$ n\~ao cont\'em \verb+bb+$\}$
       \end{list}

 \item Obtenha ER's que denotem as linguagens sobre $\{\verb+0+,\verb+1+\}$ abaixo. Dever\'a
       ser explicitado o m\'etodo ou racioc\'{\i}nio usado.
       \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 par de \verb+0+'s e \'{\i}mpar de
              \verb+1+'s.
       \end{list}

\end{enumerate}

\end{document}

