\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{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.

\section{Preliminares Matem\'{a}ticas}
 
\begin{enumerate}
 \item Prove:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$.
        \item $\overline{(A\cup B)}=(\overline{A}\cap\overline{B})$.
        \item se $A\cap B=A\cup B$, ent\~{a}o $A=B$.
       \end{list}
 \item (0.3.7 de K95) Prove que sim ou que n\~{a}o ($\mbox{\cal P}(X)$ \'{e} o conjunto
       pot\^{e}ncia de $X$):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\cal P}(A)\cap\mbox{\cal P}(B)=\mbox{\cal P}(A\cap B)$?
        \item $\mbox{\cal P}(A)\cup\mbox{\cal P}(B)=\mbox{\cal P}(A\cup B)$?
       \end{list}
 \item Que condi\c{c}\~{a}o deve ser satisfeita por duas fun\c{c}\~{o}es $f$ e $g$ para que
       $f\cup g$ seja uma fun\c{c}\~{a}o?
 \item Sejam $A$ e $B$ conjuntos de $n$ e $k$ elementos, respectivamente.
       Determine quantas fun\c{c}\~{o}es de $A$ para $B$ existem de cada um dos
       tipos: (a) totais; (b) parciais; (c) injetivas; (d) sobrejetivas; e (e)
       bijetivas.
 \item (11, cap. 1 de S88) Uma fun\c{c}\~{a}o total $f:\mbox{\bf N}\rightarrow
       \mbox{\bf N}$ \'{e} dita ser {\em monot\^{o}nica crescente\/} se $f(n)<f(n+1)$
       para todo $n\in\mbox{\bf N}$. Prove que existe um n\'{u}mero n\~{a}o cont\'{a}vel de
       fun\c{c}\~{o}es monot\^{o}nicas crescentes.
 \item (19, cap. 1 de S88) D\^{e} uma defini\c{c}\~{a}o recursiva do conjunto dos
       subconjuntos finitos de {\bf N}. Use uni\~{a}o como operador.
 \item (25, cap. 1 de S88) D\^{e} uma defini\c{c}\~{a}o recursiva do conjunto dos nodos
       de um grafo direcionado que podem ser alcan\c{c}ados a partir de um nodo
       $x$. Use a rela\c{c}\~{a}o de adjac\^{e}ncia como opera\c{c}\~{a}o.
 \item Seja uma \'{a}rvore em que cada nodo tem no m\'{a}ximo $k$ filhos. Se ela tiver
       exatamente $i$ nodos internos, quais s\~{a}o os n\'{u}meros m\'{\i}nimo e m\'{a}ximo de
       nodos que a fronteira da mesma pode ter? 
 \item (21, cap. 1 de S88) Prove, por indu\c{c}\~{a}o, que
       $\sum_{i=0}^{n}2^i=2^{n+1}-1$ para todo $n\in {\mbox N}$.
 \item (29, cap. 1 de S88) Uma {\em \'{a}rvore bin\'{a}ria completa\/} de profundidade
       $n$ \'{e} uma \'{a}rvore estritamente bin\'{a}ria na qual cada nodo nos n\'{\i}veis
       anteriores a $n$ tem filhos e cada nodo no n\'{\i}vel $n$ \'{e} uma folha. Prove
       que uma \'{a}rvore bin\'{a}ria completa de profundidade $n$ tem $2^{n+1}-1$
       nodos.
\end{enumerate}

\section{Linguagens}

\begin{enumerate}
 \item (4, cap. 2 de S88) Prove que $(w^R)^i=(w^i)^R$ para todo {\em string\/}
       $w$ e todo $i\geq 0$.
 \item (1.3.3 de K95) Quais s\~{a}o os {\em strings\/} em $\{\lambda,a\}^n$, para
       um certo $n$ arbitr\'{a}rio?
 \item (0.2.2 de AU72) Prove que sim ou que n\~{a}o: $L^+=L^*-\{\lambda\}$.
 \item (0.2.6 de AU72) Pode $L^*$ ou $L^+$ ser $\phi$? Sob quais circunst\^{a}ncias
       $L^*$ \'{e} finito? E $L^+$?
 \item (10, 13, 19, 20, 22, 23, cap. 2 de S88) D\^{e} express\~{o}es regulares que
       denotem os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ que n\~{a}o cont\^{e}m
              $aa$.
        \item o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ nos quais cada
              $b$ \'{e} seguido por pelo menos um $c$.
        \item o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais o n\'{u}mero
              $a$'s \'{e} divis\'{\i}vel por 3.
        \item o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada $a$
              \'{e} precedido (imediatamente) ou seguido (imediatamente) por $b$.
        \item o conjunto dos {\em strings\/} sobre $\{a,b\}$ com n\'{u}mero par de
              $a$'s e n\'{u}mero par de $b$'s.
        \item o conjunto dos {\em strings\/} de tamanho \'{\i}mpar sobre $\{a,b\}$
              que cont\^{e}m exatamente dois $b$'s.
       \end{list}
 \item (2.11 de HU79) Descreva, em portugu\^{e}s, os conjuntos denotados pelas
       seguintes express\~{o}es regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\boldmath $(11\cup 0)^*(00\cup 1)^*$}
        \item {\boldmath $(1\cup 01\cup 001)^*(\lambda\cup 0\cup 00)^*$}
        \item {\boldmath $[00\cup 11\cup (01\cup 10)(00\cup 11)^*(01\cup 10)]^*$}
       \end{list}
 \item (2.2.7 e 2.2.9 de K95) Simplifique as seguintes express\~{o}es regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\boldmath $\phi^*\cup a^*\cup b^*\cup (a \cup b)^*$}
        \item {\boldmath $(aa)^*a\cup (aa)^*$}
        \item {\boldmath $(a \cup b)^*a(a\cup b)^*$}
        \item {\boldmath $a(\lambda \cup aa)^*a \cup \lambda$}
        \item {\boldmath $(a\cup b)(\lambda \cup aa)^*(\lambda\cup aa) \cup a\cup b$}
        \item {\boldmath $a^*b((a\cup b)a^*b)^*(a\cup b)(aa)^*\cup a(aa)^*\cup
               a^*b((a\cup b)a^*b)^*$}
       \end{list}
\end{enumerate}

\section{Gram\'{a}ticas Livres do Contexto}
 
\begin{enumerate}
 \item (2, cap. 3 de S88) Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, ASB \,\,\,|\,\,\,
                  \lambda$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aAb \,\,\,|\,\,\,
                  \lambda$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bBa \,\,\,|\,\,\, ba$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^{e} uma deriva\c{c}\~{a}o mais a esquerda de $aabbba$.
        \item D\^{e} uma deriva\c{c}\~{a}o mais a direita de $abaabbbabbaa$.
        \item Construa as \'{a}rvores de deriva\c{c}\~{a}o para as deriva\c{c}\~{o}es das partes
              (a) e (b).
        \item Use nota\c{c}\~{a}o de conjunto para definir $L(G)$.
       \end{list}
 \item (3, cap. 3 de S88) Seja {\em AD\/} a \'{a}rvore de deriva\c{c}\~{a}o
       \begin{center}
       \begin{picture}(200,180)
        \put(100,167){\makebox(0,0)[b]{$S$}}
        \put(100,165){\line(-3,-2){60}}
        \put(100,165){\line(3,-2){60}}

        \put(40,112){\makebox(0,0)[b]{$A$}}
        \put(40,110){\line(-1,-1){40}}
        \put(40,110){\line(1,-1){40}}

        \put(160,112){\makebox(0,0)[b]{$B$}}
        \put(160,110){\line(-1,-1){40}}
        \put(160,110){\line(1,-1){40}}

        \put(0,66){\makebox(0,0)[t]{$a$}}

        \put(80,57){\makebox(0,0)[b]{$A$}}
        \put(80,55){\line(0,-1){40}}
        \put(80,11){\makebox(0,0)[t]{$a$}}

        \put(120,57){\makebox(0,0)[b]{$A$}}
        \put(120,55){\line(0,-1){40}}
        \put(120,11){\makebox(0,0)[t]{$a$}}

        \put(200,57){\makebox(0,0)[b]{$B$}}
        \put(200,55){\line(0,-1){40}}
        \put(200,13){\makebox(0,0)[t]{$b$}}
       \end{picture}
       \end{center}       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^{e} uma deriva\c{c}\~{a}o mais a esquerda que gere a \'{a}rvore {\em AD\/}.
        \item D\^{e} uma deriva\c{c}\~{a}o mais a direita que gere a \'{a}rvore {\em AD\/}.
        \item Quantas deriva\c{c}\~{o}es diferentes geram {\em AD\/}?
       \end{list}
 \item Construa uma gram\'{a}tica regular para cada uma das linguagens do exerc\'{\i}cio
       2.5 da primeira Lista.
 \item (3.3.3 de K95) Construa uma gram\'{a}tica para cada uma das linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^mb^n \,\,\,|\,\,\, m>n\}$.
        \item $\{w\in\{a,b\}^* \,\,\,|\,\,\, \mbox{o n\'{u}mero de $a$'s em $w$ \'{e} o
              dobro do n\'{u}mero de $b$'s}\}$.
        \item $\{a^mb^n \,\,\,|\,\,\, n\leq m \leq 2n\}$.
        \item $\{a^mb^nc^pd^q \,\,\,|\,\,\, m+n \geq p+q\}$.
       \end{list}
 \item (30, cap. 3 de S88) Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aSaa \,\,\,|\,\,\, B$ 
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bbBdd \,\,\,|\,\,\, C$
        \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, bd$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O que \'{e} $L(G)$?
        \item Prove que $L(G)$ \'{e} o conjunto dado em (a).
       \end{list}
 \item (4.2 de HU79) Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS \,\,\,|\,\,\, aSbS 
                  \,\,\,|\,\,\, \lambda$
       \end{enumerate}
       Prove que \[L(G)=\{x\in\{a,b\}^* \,\,\,|\,\,\, \mbox{todo prefixo de $x$
       tem no m\'{\i}nimo tantos $a$'s quantos $b$'s}\}\mbox{.}\]
       
 \item (38, cap. 3 de S88) Uma {\em gram\'{a}tica linear \`{a} direita\/} \'{e} uma
       gram\'{a}tica livre do contexto em que cada regra tem uma das formas:
       \begin{list}{(\roman{conta})}{\usecounter{conta}}
        \item $A \,\,\,\rightarrow\,\,\, w$
        \item $A \,\,\,\rightarrow\,\,\, wB$
        \item $A \,\,\,\rightarrow\,\,\, \lambda$
       \end{list}
       onde $w\in\Sigma^+$.
       
       Prove que uma linguagem $L$ \'{e} gerada por uma gram\'{a}tica linerar a direita
       se, e somente se, $L$ \'{e} gerada por uma gram\'{a}tica regular.
\end{enumerate}

\section{An\'{a}lise Sint\'{a}tica: Uma Introdu\c{c}\~{a}o}

\begin{enumerate}
 \item (3, cap. 4 de S88) Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aS \,\,\,|\,\,\, Sb
                  \,\,\,|\,\,\, ab \,\,\,|\,\,\, SS$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^{e} uma express\~{a}o regular para $L(G)$.
        \item Construa duas deriva\c{c}\~{o}es mais a esquerda de $aabb$.
        \item Construa as \'{a}rvores de deriva\c{c}\~{a}o para as deriva\c{c}\~{o}es da parte (b).
        \item Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente a $G$.
       \end{list}
 \item (7, cap. 4 de S88) Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, AaSbB \,\,\,|\,\,\,
                  \lambda$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\, a$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bB \,\,\,|\,\,\,
                  \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Defina $L(G)$ usando nota\c{c}\~{a}o de conjunto.
        \item Mostre que $G$ \'{e} amb\'{\i}gua.
        \item Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente a $G$.
       \end{list}
 \item (9, cap. 4 de S88) Construa duas gram\'{a}ticas, uma amb\'{\i}gua e outra n\~{a}o, que
       gerem a linguagem {\boldmath $a^*$}.
 \item (3.4.4 de K95) \'{E} poss\'{\i}vel ter gram\'{a}ticas regulares amb\'{\i}guas? Se sim, d\^{e}
       um exemplo. Se n\~{a}o, prove que n\~{a}o.
 \item Que rela\c{c}\~{a}o existe entre {\em grafo mais \`{a} esquerda\/} de uma gram\'{a}tica
       (def. 4.2.1 de S88) e {\em ambiguidade\/} de gram\'{a}tica?
\end{enumerate}


\section{Formas Normais}

\begin{enumerate}
 \item (3, cap. 5 de S88) Construa uma gram\'{a}tica essencialmente n\~{a}o decrescente,
       com um s\'{\i}mbolo de partida n\~{a}o recursivo, equivalente \`{a} gram\'{a}tica:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, BSA \,\,\,|\,\,\, A$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\,
                  \lambda$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, Bba \,\,\,|\,\,\,
                  \lambda$
       \end{enumerate}
 \item (14, cap. 5 de S88) Mostre que que todos os s\'{\i}mbolos da gram\'{a}tica
       abaixo s\~{a}o \'{u}teis. Construa uma gram\'{a}tica $G_C$, sem regras de cadeia,
       equivalente \`{a} mesma. Mostre que $G_C$ cont\'{e}m s\'{\i}mbolos in\'{u}teis.
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, A \,\,\,|\,\,\, CB$
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, C \,\,\,|\,\,\, D$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bB \,\,\,|\,\,\, b$
        \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC \,\,\,|\,\,\, c$
        \item[\ ] \hspace*{1cm}$D \,\,\,\rightarrow\,\,\, dD \,\,\,|\,\,\, d$
       \end{enumerate}
 \item (17, cap. 3 de S88) Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, AB \,\,\,|\,\,\, BCS$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, aA \,\,\,|\,\,\, C$
        \item[\ ] \hspace*{1cm}$B \,\,\,\rightarrow\,\,\, bbB \,\,\,|\,\,\, b$
        \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC \,\,\,|\,\,\,
                  \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma gram\'{a}tica $G_L$ essencialmente n\~{a}o decrescente,
              com um s\'{\i}mbolo de partida n\~{a}o recursivo, equivalente a $G$.
        \item Construa uma gram\'{a}tica $G_C$, sem regras de cadeias, equivalente
              a $G_L$.
        \item Construa uma gram\'{a}tica na forma normal de Chomsky equivalente
              a $G_C$.
       \end{list}
 \item (19, cap. 3 de S88) Seja $G$ uma gram\'{a}tica na forma normal de Chomsky.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Qual \'{e} o tamanho de uma deriva\c{c}\~{a}o de um {\em string\/} $w\in L(G)$
              de tamanho $n$?
        \item Qual \'{e} a profundidade m\'{a}xima de uma \'{a}rvore de deriva\c{c}\~{a}o para um
              {\em string\/} $w\in L(G)$ de tamanho $n$?
        \item Qual \'{e} a profundidade m\'{\i}nima de uma \'{a}rvore de deriva\c{c}\~{a}o para um
              {\em string\/} $w\in L(G)$ de tamanho $n$?
       \end{list}
 \item (21, cap. 3 de S88) Construa uma gram\'{a}tica na forma normal de Greibach
       equivalente \`{a} gram\'{a}tica:
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\,\,\rightarrow\,\,\, aAb \,\,\,|\,\,\, a$ 
        \item[\ ] \hspace*{1cm}$A \,\,\,\rightarrow\,\,\, SS \,\,\,|\,\,\, b$
       \end{enumerate}
 \item (27, cap. 3 de S88) Prove que toda linguagem livre do contexto \'{e} gerada
       por uma gram\'{a}tica na qual cada uma das regras \'{e} de uma das formas:
       \begin{list}{(\roman{conta})}{\usecounter{conta}}
        \item $S \,\,\,\rightarrow\,\,\, \lambda$ 
        \item $A \,\,\,\rightarrow\,\,\, a$
        \item $A \,\,\,\rightarrow\,\,\, aB$
        \item $A \,\,\,\rightarrow\,\,\, aBC$
       \end{list}
       onde $A, B, C \in V$ e $a \in \Sigma$. ({\em Sugest\~{a}o\/}: parta de uma
       gram\'{a}tica na forma normal de Greibach.)
\end{enumerate}
 
\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}
 
\section{M\'{a}quinas de Turing}
 
\begin{enumerate}
 \item (3, cap. 9 de S88) Construa uma m\'{a}quina de Turing (MT) com alfabeto de
       entrada $\{a,b\}$ para realizar cada uma das opera\c{c}\~{o}es abaixo. Note que
       o cabe\c{c}ote deve estar na posi\c{c}\~{a}o zero, no estado $q_f$, quando a
       computa\c{c}\~{a}o terminar.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Deslocar o {\em string\/} de entrada uma c\'{e}lula para a direita:
              $q_0BuB \stackrel{*}{\vdash} q_fBBuB$.
        \item Concatenar uma c\'{o}pia do reverso do {\em string\/} de entrada \`{a}
              direita do mesmo: $q_0BuB \stackrel{*}{\vdash} q_fBuu^RB$.
        \item Inserir um branco entre cada par de s\'{\i}mbolos de entrada. Exemplo:
              $q_0abaB \stackrel{*}{\vdash} q_fBaBbBaB$.
        \item Eliminar todos os $b$'s da entrada. Exemplo: $q_0babaababB
              \stackrel{*}{\vdash} q_fBaaaaB$.
       \end{list}
 \item (4, cap. 9 de S88) Construa uma MT com fita bi-direcional e alfabeto de
       entrada $\{a\}$ que pare se a fita contiver alguma c\'{e}lula sem branco.
 \item (6, cap. 9 de S88) Construa uma MT com alfabeto de entrada $\{a,b\}$ que
       aceite as seguintes linguagens por estado final:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^i \,\,\,|\,\,\, i\geq 0\}$
        \item $\{a^ib^ja^ib^j \,\,\,|\,\,\, i,j>0\}$
        \item conjunto dos {\em strings\/} com mesmo n\'{u}mero de $a$'s e $b$'s.
        \item $\{ww^R \,\,\,|\,\,\, w\in\{a,b\}^*\}$
       \end{list}
 \item (11, cap. 9 de S88) Prove que toda linguagem recursivamente enumer\'{a}vel
       \'{e} aceita por uma MT com um \'{u}nico estado de aceita\c{c}\~{a}o.
 \item (4.4.2 de K95) Construa uma MT de 3 trilhas que subtraia o n\'{u}mero bin\'{a}rio
       na sua segunda trilha do n\'{u}mero bin\'{a}rio na sua primeira trilha e deposite
       o resultado na terceira trilha.
 \item (16, cap. 9 de S88) Construa uma MT n\~{a}o determin\'{\i}stica de 2 fitas que 
       aceite os {\em strings\/} de tamanho \'{\i}mpar sobre $\{a,b,c\}$ com um $c$
       na posi\c{c}\~{a}o do meio. Toda computa\c{c}\~{a}o com entrada $w$ deve terminar ap\'{o}s,
       no m\'{a}ximo, $|w|+1$ transi\c{c}\~{o}es.
 \item (18, cap. 9 de S88) Prove que uma linguagem $L$ \'{e} recursiva se, e somente
       se, $L$ e $\bar{L}$ s\~{a}o recursivamente enumer\'{a}veis.
 \item (5.3.4 de K95) Suponha que $L_1, L_2, \ldots, L_n$ s\~{a}o linguagens que
       formam uma parti\c{c}\~{a}o de $\Sigma^*$. Se todas estas linguagens s\~{a}o
       recursivamente enumer\'{a}veis, mostre que elas t\^{e}m que ser recursivas.
 \item (4.1.3 de K95) Construa uma m\'{a}quina de Turing que enumere todos os
       inteiros bin\'{a}rios (em ordem num\'{e}rica), quando submetido o {\em string\/}
       de entrada $0$. Ou seja, a MT deve se comportar assim: \[Bq_00B
       \stackrel{*}{\vdash} Bq_01B \stackrel{*}{\vdash} Bq_010B
       \stackrel{*}{\vdash} Bq_011B \stackrel{*}{\vdash} Bq_0100B
       \stackrel{*}{\vdash} \cdots\]
       Note que esta MT n\~{a}o p\'{a}ra.
\end{enumerate}

\section{A Hierarquia de Chomsky}

\begin{enumerate}
 \item (1, cap. 10 de S88) Construa gram\'{a}ticas irrestritas para gerar as
       seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^ja^ib^j \,\,\,|\,\,\, i,j\geq 0\}$
        \item $\{a^ib^ic^idb^i \,\,\,|\,\,\, i\geq 0\}$
        \item $\{www \,\,\,|\,\,\, w\in \{a,b\}^*\}$
       \end{list}
 \item (7, cap. 10 de S88) Seja $L$ uma linguagem recursivamente enumer\'{a}vel
       sobre $\Sigma$, e $c$ um s\'{\i}mbolo terminal n\~{a}o pertencente a $\Sigma$.
       Mostre que existe uma linguagem sens\'{\i}vel ao contexto $L'$ sobre $\Sigma
       \cup\{c\}$ tal que, para todo $w\in \Sigma^*$, $w\in L$ se, e somente se,
       $wc^i\in L'$ para algum $i\geq 0$.
 \item (5.5.8 de K95) Seja {\cal C} uma classe de dispositivos de alguma
       esp\'{e}cie. Suponha que {\cal C} pode ser enumerada: $M_1$, $M_2$, \ldots.
       Suponha ainda que exista um algoritmo que, quando recebe um dispositivo
       $M$ de {\cal C} e uma entrada $w$, determina se $M$ aceita $w$. Mostre
       que nem toda linguagem recursiva sobre um alfabeto $\Sigma$ \'{e} aceita por
       algum dispositivo em {\cal C}.
 \item (12, cap. 10 de S88) Seja $u\rightarrow v$ uma regra monot\^{o}nica. Construa
       uma sequ\^{e}ncia de regras monot\^{o}nicas, cada uma com lado direito de tamanho
       2 ou menos, que defina a mesma transforma\c{c}\~{a}o que $u\rightarrow v$.
 \item (13, cap. 10 de S88) Construa uma sequ\^{e}ncia de regras sens\'{\i}veis ao
       contexto $uAv\rightarrow uwv$ que defina a mesma transforma\c{c}\~{a}o que a
       regra monot\^{o}nica $AB\rightarrow CD$. ({\em Sugest\~{a}o\/}: Uma sequ\^{e}ncia de
       3 regras, cada uma com os lados esquerdo e direito de tamanho 2, \'{e}
       suficiente.)
 \item (14, cap. 10 de S88) Use os resultados dos dois exerc\'{\i}cios anteriores
       para provar que toda linguagem sens\'{\i}vel ao contexto \'{e} gerada por uma
       gram\'{a}tica na qual cada regra tem a forma $uAv\rightarrow uwv$, onde
       $w\in (\Sigma\cup V)^+$ e $u,v\in (\Sigma\cup V)^*$.
 \item (4.4 de K95) Construa um aut\^{o}mato linear limitado que aceite a linguagem
       \[\{a^{n!} \,\,\,|\,\,\, n\geq 0\}\mbox{.}\] ({\em Sugest\~{a}o\/}: divida o {\em
       string\/} de entrada por 2, 3, 4, \ldots.)
\end{enumerate}

\section{Decidibilidade}

\begin{enumerate}
 \item (7, cap. 11 de S88) Dada uma MT arbitr\'{a}ria $M$ e um {\em string\/} de
       entrada $w$, ir\'{a} a computa\c{c}\~{a}o de $M$ com entrada $w$ parar em menos de
       100 transi\c{c}\~{o}es? Descreva uma MT que resolva este problema de decis\~{a}o.
 \item (6.1.1 de K95) Mostre que se o problema da parada \'{e} decid\'{\i}vel ent\~{a}o toda
       linguagem recursivamente enumer\'{a}vel \'{e} recursiva.
 \item (9, cap. 11 de S88) Prove que n\~{a}o existe algoritmo que determine se uma
       MT arbitr\'{a}ria ir\'{a} parar para alguma entrada. Isto \'{e}, $R(M)$ \'{e} aceito
       se $M$ parar para algum {\em string\/} $w$; caso contr\'{a}rio, $R(M)$ \'{e}
       rejeitado.
 \item (10, cap. 11 de S88) Prove que n\~{a}o existe algoritmo que determine se uma
       MT arbitr\'{a}ria ir\'{a} parar para todos os {\em strings\/} de entrada.
 \item (11, cap. 11 de S88) Prove que n\~{a}o existe algoritmo que receba como
       entrada uma MT $M=(Q,\Sigma,\Gamma,\delta,q_0,F)$, um estado $q_i\in Q$,
       e um {\em string\/} $w\in\Sigma^*$, e determine se a computa\c{c}\~{a}o de $M$
       com entrada $w$ entra no estado $q_i$.
 \item (6.1.4 de K95) Prove que n\~{a}o existe algoritmo que determine se 
       $L(M)=\phi$, para uma MT arbitr\'{a}ria $M$.  ({\em Sugest\~{a}o\/:} reduzir o
       problema da fita em branco a este.)
 \item (15, cap. 11 de S88) Prove que o problema da correspond\^{e}ncia de Post para
       sistemas com alfabeto de um \'{u}nico s\'{\i}mbolo \'{e} decid\'{\i}vel.
 \item (6.3.1 de K95) Sejam $G_1$ uma gram\'{a}tica regular arbitr\'{a}ria e $G_2$ uma
       gram\'{a}tica livre do contexto arbitr\'{a}ria. \'{E} decid\'{\i}vel o problema de
       determinar se $L(G_1)\cap L(G_2)=\phi$?
 \item (17, cap. 11 de S88) Prove que n\~{a}o existe algoritmo que determine se a
       interse\c{c}\~{a}o das linguagens de duas gram\'{a}ticas livres do contexto cont\'{e}m
       um n\'{u}mero infinito de elementos.
 \item (18, cap. 11 de S88) Prove que n\~{a}o existe algoritmo que determine se o
       complemento da linguagens de uma gram\'{a}tica livre do contexto cont\'{e}m
       um n\'{u}mero infinito de elementos.
\end{enumerate}

\end{document}
\endinput
\end

