\documentclass[12pt, a4paper]{report}
\newcounter{conta}

\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2001 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Segunda Lista de Exerc\'{\i}cios } \hfill Devolu\c c\~ao: 20/02/02

\begin{enumerate}

 \item Construa AFN's que reconhe\c cam as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{x\verb+1+y\verb+1+z \,\,|\,\, x,y,z\in\{\verb+0+,\verb+1+\}^* \mbox{ e 
                    $|x|$, $|y|$ e $|z|$ s\~ao \'{\i}mpares}\}$
        \item $\{xyx\,\,|\,\, x,y\in\{\verb+a+,\verb+b+\}^* \mbox{ e } |x|=2\}$.
        \item $\{w\,\,|\,\, \verb+00+ \mbox{ n\~ao aparece nos 4 \'ultimos s\'{\i}mbolos de
               $w$}\}$.
       \end{list}

 \item Obtenha AFD's equivalentes aos 2 primeiros AFN's 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}
       Construa um AFN equivalente.

 \item Para cada express\~ao regular abaixo, obtenha uma gram\'atica regular que gere
       a linguagem denotada por ela.
       \begin{enumerate}
        \item[(a)] $(1+011)^*$
        \item[(b)] $(01)^*(10)^*$
       \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 \verb+c+ x \,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$
        \item $\{xx \,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$
        \item $\{\verb+0+^{n^2}\,\,|\,\, n\geq0\}$
       \end{list}

 \item Prove que os seguintes conjuntos s\~ao ou n\~ao s\~ao linguagens regulares,
       utilizando propriedades de fechamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\, m<n\}\cup\{\verb+0+^m\verb+1+^n\,\,|\,\,
               m>n\}$
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\, m<n\}\cup\{\verb+0+^m\verb+1+^n\,\,|\,\, m>n\}
               \cup\{\verb+0+^n\verb+1+^n\,\,|\,\, n\geq 0\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ o n\'umero de \verb+0+'s em $w$ \'e
              duas vezes o de \verb+1+'s$\}$
        \item $\{\verb+a+^n\verb+b+^k\,\,|\,\,n\not=k\}$
        \item $\{\verb+0+^m\verb+1+^n\verb+2+^{m+n}\,\,|\,\, m,n>0\}$
       \end{list}
       Se n\~ao conseguir, use o lema do bombeamento.

 \item Mostre que a classe das linguagens regulares \'e fechada sob as seguintes
       opera\c c\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pref\/}(L)=\{x \,\,|\,\, xy\in L \}$ (os prefixos das palavras
               de $L$)
        \item $\mbox{\em suf\/}(L)=\{y \,\,|\,\, xy\in L \}$ (os sufixos das palavras de $L$)
        \item $\mbox{\em rev\/}(L)=\{w^R \,\,|\,\, w\in L\}$ (os reversos das palavras de
               $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 Encontre ER's e GR's para os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, 2\leq |w|\leq 5\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ cont\'em \verb+a+ e tem tamanho
              par$\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\,$ \verb+a+'s s\'o podem ocorrer nas
              posi\c c\~oes pares de $w\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ cont\'em exatamente um \verb+bb+$\}$
       \end{list}

 \item Obtenha ER's que denotem as seguintes linguagens sobre $\{\verb+0+,\verb+1+\}$ a partir
       de um AFD para as mesmas, usando o m\'etodo visto em aula:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que come\c cam com \verb+1+ e terminam com \verb+1+.
        \item O conjunto das palavras com n\'umeros \'{\i}mpar de \verb+0+'s e \'{\i}mpar de
              \verb+1+'s.
       \end{list}

\end{enumerate}

\end{document}


