\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Terceira Lista de Exerc\'{\i}cios}

\vspace*{3mm}
\noindent \underline{Observa\c{c}\~{a}o}: Os n\'{u}meros dos exerc\'{\i}cios extra\'{\i}dos de livros
indicados no Plano de Curso est\~{a}o apresentados seguidos das iniciais dos autores
concatenadas com os dois \'{u}ltimos d\'{\i}gitos do ano da publica\c{c}\~{a}o do livro.

\setcounter{section}{5}

\section{Aut\^{o}matos Finitos}
 
\begin{enumerate}
 \item Construa um aut\^{o}mato finito determin\'{\i}stico (AFD) para cada uma das
       linguagens do e\-xer\-c\'{\i}\-cio 2.5 da primeira Lista.
 \item (11, cap. 6 de S88) Construa um AFD para cada uma das linguagens:
       
       \begin{tabular}{rlrlrl}
        (a) & {\boldmath $(ab)^*ba$} & (b) & {\boldmath $(ab)^*(ba)^*$} 
        \ \ \ \ \ \ &
        (c) & {\boldmath $aa(a\cup b)^+bb$} \\
        (d) & {\boldmath $((aa)^+bb)^*$} \ \ \ \ \ \ & (e) & {\boldmath $(ab^*a)^*$} \\
       \end{tabular}
 \item (16 a 19, cap. 6 de S88) Construa um aut\^{o}mato finito n\~{a}o determin\'{\i}stico
       (AFN) para cada uma das linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada
              {\em substring\/} de tamanho 4 tem pelo menos um $b$.
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada
              {\em substring\/} de tamanho 4 tem exatamente um $b$.
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais o terceiro
              s\'{\i}mbolo da direita para a esquerda \'{e} $b$.
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ que cont\^{e}m um n\'{u}mero
              par de {\em substrings\/} $ba$.
       \end{list}
 \item (21, cap. 6 de S88) Construa um AFD que reconhe\c{c}a o conjunto dos {\em
       strings\/} sobre $\{a,b\}$ terminados em $abba$. Construa um diagrama de
       estados de um AFN, com seis arcos, que reconhe\c{c}a a mesma linguagem.
 \item (22, cap. 6 de S88) Seja o AFN-$\lambda$ $M=(\{q_0,q_1,q_2\},
       \{a,b,c\},\delta,q_0,\{q_1,q_2\})$, sendo $\delta$ dada por:
       \begin{center}
       \begin{tabular}{c|cccc}
       $\delta$ & $a$ & $b$ & $c$ & $\lambda$ \\ \hline
       $q_0$ & $\{q_0\}$ & $\phi$ & $\{q_1\}$ & $\{q_2\}$ \\
       $q_1$ & $\phi$ & $\phi$ & $\{q_1\}$ & $\phi$ \\
       $q_2$ & $\phi$ & $\{q_1,q_2\}$ & $\phi$ & $\phi$
       \end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^{e} uma express\~{a}o regular para $L(M)$.
        \item Determine $\lambda$-{\em fecho\/}$(q_i)$ para $i=0,1,2$.
        \item D\^{e} a fun\c{c}\~{a}o de transi\c{c}\~{a}o $t$ para $M$.
        \item Construa um AFD equivalente a $M$ usando o algoritmo 6.6.3 de
              S88.
       \end{list}
 \item Seja o AFN-$\lambda$ $M=(\{q_0,q_1,q_2\},\{a,b,c\},\delta,q_0,\{q_2\})$,
       sendo $\delta$ dada por:
       \begin{center}
       \begin{tabular}{c|cccc}
       $\delta$ & $a$ & $b$ & $c$ & $\lambda$ \\ \hline
       $q_0$ & $\{q_0\}$ & $\phi$ & $\phi$ & $\{q_1\}$ \\
       $q_1$ & $\phi$ & $\{q_1\}$ & $\phi$ & $\{q_2\}$ \\
       $q_2$ & $\phi$ & $\phi$ & $\{q_2\}$ & $\phi$
       \end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^{e} uma express\~{a}o regular para $L(M)$.
        \item Determine $\lambda$-{\em fecho\/}$(q_i)$ para $i=0,1,2$.
        \item D\^{e} a fun\c{c}\~{a}o de transi\c{c}\~{a}o $t$ para $M$.
        \item Construa um AFD equivalente a $M$ usando o algoritmo 6.6.3 de
              S88.
       \end{list}
 \item (25, cap. 6 de S88) Fa\c{c}a uma defini\c{c}\~{a}o recursiva da fun\c{c}\~{a}o de transi\c{c}\~{a}o
       estendida $\hat{\delta}$ de um AFN-$\lambda$. O valor
       $\hat{\delta}(q_i,w)$ \'{e} o conjunto dos estados que podem ser alcan\c{c}ados
       por computa\c{c}\~{o}es que come\c{c}am no nodo $q_i$ e processam completamente o
       {\em string\/} $w$.
       
 \item (2.8.12 de K95) Determine uma express\~{a}o regular para a linguagem aceita
       pelo aut\^{o}mato finito $(\{q_0,q_1, \ldots, q_{10}\},\{a,b\},\delta,q_0,
       \{q_4,q_{10}\})$, onde $\delta$ \'{e} dada por:
       \begin{center}
       \begin{tabular}{c|cc}
       $\delta$ & $a$ & $b$  \\ \hline
       $q_0$ & $\{q_1\}$ & $\phi$  \\
       $q_1$ & $\{q_2\}$ & $\{q_5\}$ \\
       $q_2$ & $\{q_3\}$ & $\{q_6\}$ \\
       $q_3$ & $\{q_4\}$ & $\{q_7\}$ \\
       $q_4$ & $\phi$ & $\phi$ \\
       $q_5$ & $\{q_8\}$ & $\{q_6\}$ \\
       $q_6$ & $\{q_9\}$ & $\{q_7\}$ \\
       $q_7$ & $\phi$ & $\{q_4\}$ \\
       $q_8$ & $\{q_9\}$ & $\{q_{10}\}$ \\
       $q_9$ & $\{q_7\}$ & $\{q_{10}\}$ \\
       $q_{10}$ & $\phi$ & $\phi$ 
       \end{tabular}
       \end{center}
       usando o algoritmo 6.8.2 de S88.
 \item (2.8.14 de K95) Determine uma express\~{a}o regular para as linguagens
       aceitas pelos seguintes aut\^{o}matos finitos (use a t\'{e}cnica do algoritmo
       6.8.2 de S88):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{q_1, q_2, q_3\},\{a,b\},\delta_1,q_1, \{q_2\})$, onde
        $\delta_1$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_1$ & $a$ & $b$  \\ \hline
         $q_1$ & $q_2$ & $q_2$ \\
         $q_2$ & $q_3$ & $q_1$ \\
         $q_3$ & $q_2$ & $q_2$
        \end{tabular}
        \end{center}
        \item $(\{q_1, q_2, q_3\},\{a,b\},\delta_2,q_1, \{q_1\})$, onde
        $\delta_2$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_2$ & $a$ & $b$  \\ \hline
         $q_1$ & $q_1$ & $q_3$ \\
         $q_2$ & $q_1$ & $q_3$ \\
         $q_3$ & $q_2$ & $q_3$
        \end{tabular}
        \end{center}
        \item $(\{q_1, q_2, q_3\},\{a,b\},\delta_3,q_1, \{q_2,q_3\})$, onde
        $\delta_3$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_3$ & $a$ & $b$  \\ \hline
         $q_1$ & $q_3$ & $q_2$ \\
         $q_2$ & $q_3$ & $q_1$ \\
         $q_3$ & $q_1$ & $q_2$
        \end{tabular}
        \end{center}
        \item $(\{q_1, q_2, q_3,q_4,q_5\},\{a,b\},\delta_4,q_1, \{q_5\})$, onde
        $\delta_4$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_4$ & $a$ & $b$  \\ \hline
         $q_1$ & $q_2$ & $q_1$ \\
         $q_2$ & $q_2$ & $q_3$ \\
         $q_3$ & $q_4$ & $q_1$ \\
         $q_4$ & $q_5$ & $q_3$ \\
         $q_5$ & $q_5$ & $q_5$
        \end{tabular}
        \end{center}
        \item $(\{q_1, q_2, q_3,q_4\},\{a,b\},\delta_5,q_1, \{q_3\})$, onde
        $\delta_5$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_5$ & $a$ & $b$  \\ \hline
         $q_1$ & $\{q_2\}$ & $\{q_4\}$ \\
         $q_2$ & $\phi$ & $\{q_3,q_4\}$ \\
         $q_3$ & $\{q_3\}$ & $\{q_3\}$ \\
         $q_4$ & $\{q_2,q_4\}$ & $\phi$
        \end{tabular}
        \end{center}
       \end{list}
\end{enumerate}

\section{Linguagens e Conjuntos Regulares}

\begin{enumerate}
 \item (2, cap.7 de S88) Use o corol\'{a}rio 7.2.2 de S88 para mostrar que os
       seguintes conjuntos n\~{a}o s\~{a}o regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ com o mesmo n\'{u}mero
              de $a$'s e $b$'s.
        \item Conjunto dos pal\'{\i}ndromos sobre $\{a,b\}$ de tamanho par.
        \item Conjunto dos {\em strings\/} sobre $\{(,)\}$ nos quais cada ``(''
              tem um ``)'' correspondente.
        \item $\{a^i(ab)^j(ca)^{2i} \,\,\,|\,\,\, i,j>0\}$.
       \end{list}
 \item (3(a, b, c), cap. 7 de S88) Use o {\em pumping lemma\/} para mostrar que
       os seguintes conjuntos n\~{a}o s\~{a}o regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto dos pal\'{\i}ndromos sobre $\{a,b\}$.
        \item $\{a^nb^m \,\,\,|\,\,\, n<m\}$.
        \item $\{ww \,\,\,|\,\,\, w\in\{a,b\}^*\}$.
       \end{list}
 \item (5, cap.7 de S88) Seja $L$ uma linguagem regular sobre $\{a,b,c\}$.
       Mostre que cada um dos seguintes conjuntos \'{e} regular:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \,\,\,|\,\,\, w\in L \mbox{ e } w \mbox{ cont\'{e}m algum $a$}\}$.
        \item $\{w \,\,\,|\,\,\, w\in L \mbox{ ou } w \mbox{ cont\'{e}m algum $a$}\}$.
        \item $\{w \,\,\,|\,\,\, w\not\in L \mbox{ e } w \mbox{ n\~{a}o cont\'{e}m
              $a$'s}\}$.
       \end{list}
 \item (7, cap.7 de S88) Seja $L$ uma linguagem regular. Mostre que cada uma das
       seguintes lingaugens \'{e} regular:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto $P=\{u \,\,\,|\,\,\, uv\in L\}$ dos prefixos de $L$.
        \item O conjunto $S=\{v \,\,\,|\,\,\, uv\in L\}$ dos sufixos de $L$.
        \item O conjunto $L^R=\{w^R \,\,\,|\,\,\, w\in L\}$ dos reversos de $L$.
        \item O conjunto $E=\{uv \,\,\,|\,\,\, v\in L\}$ dos {\em strings\/}
              que t\^{e}m sufixos em $L$.
       \end{list}
 \item (8, cap.7 de S88) Seja $L$ uma linguagem regular que s\'{o} tem {\em
       strings\/} de tamanho par. Seja $L'=\{u \,\,\,|\,\,\, uv\in L \mbox{ e }
       |u|=|v|\}$. Prove que $L'$ \'{e} regular.
 \item (9, cap.7 de S88) Sejam $\Sigma_1$ e $\Sigma_2$ dois alfabetos. Um
       {\em homomorfismo\/} \'{e} uma fun\c{c}\~{a}o total $h:\Sigma_1^*\rightarrow
       \Sigma_2^*$ que preserva concatena\c{c}\~{a}o. Ou seja, $h$ satisfaz:
       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item $h(\lambda)=\lambda$
        \item $h(uv)=h(u)h(v)$.
       \end{list}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja $L_1\in\Sigma_1^*$ uma linguagem regular. Mostre que
              $\{h(w) \,\,\,|\,\,\, w\in L_1\}$ \'{e} regular sobre $\Sigma_2^*$. Tal
              conjunto \'{e} denominado {\em imagem homom\'{o}rfica\/} de $L_1$ sob $h$.
        \item Seja $L_2\in\Sigma_2^*$ uma linguagem regular. Mostre que
              $\{w\in \Sigma_1^* \,\,\,|\,\,\, h(w)\in L_2\}$ \'{e} regular. Tal
              conjunto \'{e} denominado {\em imagem inversa\/} de $L_2$ sob $h$.
       \end{list}
 \item (11, cap.7 de S88) Uma gram\'{a}tica livre do contexto $G=(V,\Sigma,P,S)$ \'{e}
       denominada {\em regular \`{a} esquerda\/} se cada uma de suas regras \'{e} de
       uma das formas:
       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item $A \,\,\,\rightarrow\,\,\, \lambda$
        \item $A \,\,\,\rightarrow\,\,\, a$
        \item $A \,\,\,\rightarrow\,\,\, Ba$
       \end{list}
       onde $A,B\in V$ e $a\in\Sigma$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Fa\c{c}a um algoritmo para construir um AFN que aceite a linguagem
              gerada por uma gram\'{a}tica regular \`{a} esquerda.
        \item Mostre que as gram\'{a}ticas regulares \`{a} esquerda geram exatamente os
              conjuntos regulares.
       \end{list}
\end{enumerate}

\section{Aut\^{o}matos a Pilha e Linguagens Livres do Contexto}

\begin{enumerate}
 \item (3(c, g, h, i), cap. 8 de S88) Construa aut\^{o}matos a pilha (AP) para as
       seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^jc^k \,\,\,|\,\,\, i+k=j\}$
        \item $\{a^ib^jc^k \,\,\,|\,\,\, i=j \mbox{ ou } j=k\}$
        \item $\{a^ib^j \,\,\,|\,\,\, i\not=j\}$
        \item $\{a^ib^j \,\,\,|\,\,\, i\leq j\leq 2i\}$
       \end{list}
 \item (3.7.7 de K95) Encontre um AP que aceite $aa^*ba$. A presen\c{c}a de um
       dispositivo de mem\'{o}ria em um aut\^{o}mato pode permitir uma certa economia
       de estados. Um aut\^{o}mato finito para a linguagem acima tem,
       necessariamente, no m\'{\i}nimo 4 estados, e consequentemente um AP para a
       mesma linguagem, que ignore a pilha, deve ter tamb\'{e}m no m\'{\i}nimo 4 estados.
       Encontre um AP para $aa^*ba$ com apenas 2 estados.
 \item (5, cap. 8 de S88) Use a t\'{e}cnica do teorema 8.3.1 de S88 para construir um AP
       que aceite a linguagem gerada pela gram\'{a}tica:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aABA \,\,\,|\,\,\,
                  aBB$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, bA \,\,\,|\,\,\, b$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, cB \,\,\,|\,\,\, c$
       \end{enumerate}
 \item (10, cap.8 de S88) Seja $L$ a linguagem $\{w\in\{a,b\}^*\,\,\,|\,\,\, 
       w$ tem prefixo contendo mais $b$'s que $a$'s$\}$. Por exemplo,
       $baa, abba, abbaaa\in L$, mas $aab, aabbab\not\in L$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AP que aceite $L$ por estado final.
        \item Construa um AP que aceite $L$ por pilha vazia.
       \end{list}
 \item (12(a, c, e), cap. 8 de S88) Use o {\em pumping lemma\/} para mostrar que
       as seguintes linguagens n\~{a}o s\~{a}o livres do contexto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^k \,\,\,|\,\,\, k \mbox{ \'{e} um quadrado perfeito}\}$.
        \item $\{a^ib^{2i}a^i \,\,\,|\,\,\, i\geq 0\}$.
        \item $\{ww^Rw \,\,\,|\,\,\, w\in \{a,b\}^*\}$.
       \end{list}
 \item (3.8.12 de K95) Mostre que $\{a^nb^n\,\,\,|\,\,\, n\geq 0 \mbox{ e $n$
       n\~{a}o \'{e} m\'{u}ltiplo de 5}\}$ \'{e} uma linguagem livre do contexto.
 \item (16, cap.8 de S88)
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFD $N$ que aceite os {\em strings\/} de $\{a,b\}^*$
              com n\'{u}mero \'{\i}mpar de $a$'s.
        \item Construa um AP $M$ que aceite $\{a^{3i}b^i \,\,\,|\,\,\, i\geq 0
              \}$.
        \item Use a t\'{e}cnica do teorema 8.5.3 de S88 para construir um AP que
              aceite $L(N)\cap L(M)$.
       \end{list}
 \item (3.8.13 de K95) Seja $L=\{a^ib^jc^k \,\,\,|\,\,\, i\not=j \mbox{ ou }
       j\not=k\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $L$ \'{e} uma linguagem livre do contexto.
        \item Mostre que se $\Sigma$ \'{e} qualquer alfabeto tal que $L\subseteq
              \Sigma^*$, ent\~{a}o $\Sigma^*-L$ n\~{a}o \'{e} uma linguagem livre do
              contexto. ({\em Sugest\~{a}o\/}: considere a linguagem {\boldmath
              $a^*b^*c^*$}.)
       \end{list}
 \item (23, cap.8 de S88) Prove que o conjunto das linguagens livres do
       contexto \'{e} fechado sob reverso.
\end{enumerate}
 
\end{document}
\endinput
\end
                            


