\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 Quarta Lista de Exerc\'{\i}cios } \hfill Devolu\c c\~ao: 17/04/02

\begin{enumerate}

 \item Obtenha um AP que reconhe\c ca a linguagem do Exerc\'{\i}cio 2(b), a partir
       da GLC de tal  linguagem, usando o m\'etodo apresentado no curso.

 \item Seja o aut\^{o}mato a pilha $P = (\{i\},\{\verb+(+,\verb+)+\},\{\verb+0+\},
      \delta,\{i\},\{i\})$ tal que $\delta$ \'{e} dada por:
       \begin{center}
       \begin{tabular}{ccc}
        $\delta(i,\verb+(+,\lambda)$ & $=$ & $[i,\verb+0+]$ \\
        $\delta(i,\verb+)+,\verb+0+)$ & $=$ & $[i,\lambda]$
       \end{tabular}
       \end{center}
       Construa uma gram\'{a}tica livre do contexto que gere $L(P)$, utilizando
       o m\'{e}todo visto no curso.

 \item Sejam $L_1=\{\verb+a+^n\verb+b+^n \,\,|\,\, n\geq 0\}$ e
       $L_2=\{w\in\{\verb+a+,\verb+b+\}^* \,\,|\,\, |w| \mbox{ \'{e} m\'{u}ltiplo
       de 5}\}$. Mostre, para cada linguagem abaixo, que ela \'e ou n\~ao uma
       linguagem livre do contexto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\overline{L_1}$
        \item $L_1\cap L_2$
        \item $L_1\cap \overline{L_2}$
       \end{list}

 \item Mostre que sim ou que n\~ao: as linguagens livres do contexto s\~ao fechadas
       sob diferen\c ca.

 \item Prove que as seguintes afirmativas s\~{a}o ou n\~ao verdadeiras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'{e} uma linguagem livre do contexto e $F$ \'{e} finita,
              ent\~{a}o $L-F$ \'{e} linguagem livre do contexto.
        \item Se $L$ \'{e} uma linguagem livre do contexto e $R$ \'{e} regular,
              ent\~{a}o $L-R$ \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $F$ \'{e}
              finita, ent\~{a}o $L-F$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $R$ \'{e}
              regular, ent\~{a}o $L-R$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $F$ \'{e}
              finita, ent\~{a}o $L\cup F$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $R$ \'{e}
              regular, ent\~{a}o $L\cup R$ n\~{a}o \'{e} linguagem livre do
              contexto.
       \end{list}

 \item Construa uma MT que, dada uma palavra na base 2, soma 1 \`a mesma.

 \item Construa uma MT que aceite a linguagem denotada pela express\~ao regular
       $\verb+0+^+$, sendo $\{\verb+0+,\verb+1+\}$ o alfabeto da linguagem,
       usando um n\'umero m\'{\i}nimo de transi\c c\~oes.

 \item Construa uma MT que reconhe\c ca a linguagem:
       \[\{\verb+0+^{k_0}\verb+1+\verb+0+^{k_1}\verb+1+\ldots\verb+0+^{k_n}\verb+1+
         \,\,|\,\,n\in\mbox{\bf N} \mbox{ e } 0<k_0<k_1<\cdots<k_n\}\mbox{.}\]
       Use uma fita s\'o para assegurar a condi\c c\~ao $0<k_0<k_1<\cdots<k_n$.

 \item Construa MT's (de qualquer um dos tipos abordados, inclusive combinados) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^{2n}\verb+1+^n\,\,|\,\, n\geq 0\}$
        \item $\{\verb+0+^n\verb+1+^n\verb+2+^n\,\,|\,\, n\geq 0\}$
       \end{list}
       Restri\c c\~oes: (1) passar sobre a entrada apenas uma vez, e (2) especificar
       o menor n\'umero poss\'{\i}vel de transi\c c\~oes.

 \item Construa MT's (de qualquer um dos tipos abordados, inclusive combinados) {\em n\~ao
       determin\'{\i}sticas\/} que reconhe\c cam:
       \[\{xww^Ry\,\,|\,\, x,y,w\in\{\verb+a+,\verb+b+\}^* \mbox{ e }
         |x|\geq |y|\}\mbox{.}\]

 \item Construa uma GSC que aceite e um ALL que reconhe\c ca 
       \[\{\verb+a+^m\verb+b+^n\verb+c+^k\,\,|\,\,m>n>k\}\mbox{.}\]

 \item Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\overline{L}$ n\~ao \'e recursiva.
        \item Se $L$ \'e LRE, ent\~ao $\overline{L}$ n\~ao \'e LRE.
       \end{list}

 \item Sejam $L$ uma LRE e $R$ uma linguagem recursiva.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $L-R$ \'e uma LRE.
        \item $L-R$ \'e recursiva?
        \item $R-L$ \'e LRE?
       \end{list}

\end{enumerate}

\end{document}
