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

\begin{enumerate}

 \item Construa AFNs 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 $\{x{\tt 00}y\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, n_{\verb+1+}(x) \mbox{ mod } 3 = 0
               \mbox{ e } \eta(y) \mbox{ mod } 3=0\}$, 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+\}^*$, exceto $\lambda$,
              em que o \'ultimo s\'{\i}mbolo n\~ao tenha ocorrido antes. (Dica: use v\'arios estados
              iniciais.)
        \item Modifique o AFN do item anterior para que ele aceite tamb\'em $\lambda$,
              sem acrescentar nenhum estado e nenhuma transi\c c\~ao, se poss\'{\i}vel.
       \end{list}
 
 \item Obtenha AFDs equivalentes aos AFN dos itens (b) e (c) da quest\~ao anterior, usando o
       m\'etodo visto em aula ({\em subset construction\/}).

 \item Seja o AFNE $M=(\{1,2,3,4\},\{\verb+0+,\verb+1+\},\delta,\{1\},\{3,4\})$,
       onde $\delta$ \'e dada por:
       \begin{center}
        \begin{tabular}{c|cccccc}
         $\delta$ & \verb+0+ & \verb+1+ &  $\lambda$ & {\tt 00} & {\tt 01} & {\tt 11}\\ \hline
              $1$ & $\{2\}$  & $\{\}$   & $\{\}$   & $\{\}$     & $\{\}$   & $\{\}$  \\
              $2$ & $\{\}$   & $\{3\}$  & $\{4\}$  & $\{\}$     & $\{2\}$  & $\{\}$  \\
              $3$ & $\{\}$   & $\{\}$   & $\{\}$   & $\{\}$     & $\{\}$   & $\{\}$   \\
              $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 $\{\verb+0+^ny\,\,|\,\, n\geq 0, y\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |y|=n\}$.
        \item $\{{\tt 0}^k{\tt 1}^n\,\,|\,\, k>2n\}$.
        \item $\{\verb+0+^{n^2}\,\,|\,\, n\geq0\}$.
       \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 $F$ uma linguagem finita. Mostre que sim ou que
       n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L\cup F$ \'e uma linguagem n\~ao regular.
        \item $L-F$ \'e uma linguagem n\~ao regular.
        \item $LF$ \'e uma linguagem n\~ao regular.
       \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 $R$ pode ser subconjunto de $L$.
        \item $L$ pode ser subconjunto de $R$.
        \item Todo subconjunto de $R$ \'e linguagem regular.
        \item $L$ \'e infinita.
        \item $L\cup R$ \'e uma linguagem n\~ao regular.
        \item $L-R$ \'e uma linguagem n\~ao regular.
        \item $LR$ \'e uma linguagem n\~ao regular.
       \end{list}

 \item Encontre ERs e GRs para os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,|\, |w|\in \{0,2,4\}\}$.
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,|\, w$ tem um n\'umero par de {\tt ab}s$\}$.
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,|\, w$ cont\'em exatamente um \verb+aa+$\}$.
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,|\, w$ n\~ao cont\'em \verb+aa+$\}$.
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,|\, w$ cont\'em \verb+b+ e $|w| \mbox{ mod } 3=1\}$.
       \end{list}

 \item Obtenha ERs que denotem as linguagens sobre $\{\verb+0+,\verb+1+\}$ abaixo, a partir
       de AFs que reconhe\c cam as mesmas, usando o m\'etodo visto em aula. N\~ao simplifique
       as ERs.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras em que os 3 primeiros s\'{\i}mbolos n\~ao cont\^em
             \verb+00+.
        \item O conjunto das palavras que n\~ao cont\'em a subpalavra \verb+000+.
        \item O conjunto das palavras com pelo menos um \verb+0+ e com n\'umero \'{\i}mpar de
              \verb+1+s.
       \end{list}

 \item Responda \`as seguintes perguntas, justificando suas respostas:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item Quantas regras, no m\'{\i}nimo, s\~ao necess\'arias para gerar uma linguagem
                infinita?
          \item Dada uma GR, \'e poss\'{\i}vel obter uma express\~ao regular que denota a linguagem
                gerada por ela?
          \item \'E poss\'{\i}vel denotar qualquer linguagem finita por meio de ER?
          \item Dada uma GR \'e poss\'{\i}vel obter uma outra GR equivalente em que a
                gera\c c\~ao de qualquer palavra \'e determin\'{\i}stica (em qualquer passo
                da deriva\c c\~ao existe uma \'unica regra aplic\'avel)?
         \end{list}

\end{enumerate}

\end{document}
