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

\begin{enumerate}
 \item Construa APD's para as seguintes linguagens:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{w\verb+0+w^R\,\,|\,\,w\in\{\verb+1+,\verb+2+\}^*\}$
          \item $\{\verb+0+^n\verb+1+^n0^k\,\,|\,\,n\geq 1 \mbox{ e } k\geq 0\}$
          \end{list}

 \item Explique porque n\~ao h\'a APD para as seguintes linguagens:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{ww^R\,\,|\,\,w\in\{\verb+1+,\verb+2+\}^*\}$
          \item $\{\verb+0+^n\verb+1+^n0^k\,\,|\,\,n,k\geq 0\}$
         \end{list}

 \item Construa APN's que reconhe\c cam as linguagens seguintes por estado final e
       pilha vazia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+^k\,\,|\,\,n\leq k\leq 2n\}$
        \item $\{\verb+0+^n\verb+1+^n\verb+0+^k\,\,|\,\,n,k\geq 0\}$
       \end{list}

 \item Construa APN's que reconhe\c cam as linguagens do exerc\'{\i}cio 2:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item por estado final;
          \item por pilha vazia.
         \end{list}

 \item Construa GLC's para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=\{\verb+0+^n\verb+1+^k\,\,|\,\, 2n\leq k \leq 3n\}$
        \item $L_2=\{\verb+a+^n\verb+b+^k\verb+c+^m\,\,|\,\,k=2n+m\}$
        \item $(L_1\cup L_2)^2$
       \end{list}

 \item Seja a gram\'atica $G$:
       \begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $\verb+a+ P \verb+b+ \,\,|\,\, \verb+a+ \verb+a+ P 
                               \verb+b+ \,\,|\,\, \lambda$
	\end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ \'e amb\'{\i}gua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item Construa uma gram\'atica sem regras $\lambda$ equivalente
	\`a seguinte gra\-m\'a\-ti\-ca:
	\begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $B P A \,\,|\,\, A$ \\
	 $A$ & $\rightarrow$ & $\verb+a+ A \,\,|\,\, \lambda$ \\
	 $B$ & $\rightarrow$ & $B \verb+b+ \verb+a+ \,\,|\,\, \lambda$
	\end{tabular}
	\end{center}

  \item Seja a gram\'atica $G$:
	\begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $A \,\,|\,\, B C $ \\
	 $A$ & $\rightarrow$ & $B \,\,|\,\, C$ \\
	 $B$ & $\rightarrow$ & $\verb+b+ B \,\,|\,\, \verb+b+$ \\
	 $C$ & $\rightarrow$ & $\verb+c+ C \,\,|\,\, \verb+c+$ \\
	\end{tabular}
	\end{center}
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item Construa uma gram\'atica equivalente a $G$, sem regras de
	       cadeias.
	 \item Mostre que a gram\'atica constru\'{\i}da cont\'em s\'{\i}mbolos
	       in\'uteis.
	\end{list}

 \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 Seja um AP cuja pilha pode conter, no m\'aximo, $n$ s\'{\i}mbolos. Que
       limita\c c\~oes ter\'a tal tipo de AP? Justifique sua resposta.

 \item Quantas deriva\c c\~oes levam \`a AD abaixo?

\begin{center}
\begin{picture}(160,228)

\put(60,228){\oval(16,16){\makebox(0,0){$E$}}}

\put(60,220){\line(0,-1){28}}

\put(60,184){\oval(16,16){\makebox(0,0){$T$}}}

\put(56,178){\line(-1,-1){32}}
\put(60,176){\line(0,-1){28}}
\put(64,178){\line(1,-1){32}}

\put(20,140){\oval(16,16){\makebox(0,0){$T$}}}
\put(60,140){\oval(16,16){\makebox(0,0){$*$}}}
\put(100,140){\oval(16,16){\makebox(0,0){$F$}}}

\put(20,132){\line(0,-1){28}}
\put(20,96){\oval(16,16){\makebox(0,0){$F$}}}

\put(96,134){\line(-1,-1){32}}
\put(100,132){\line(0,-1){28}}
\put(104,134){\line(1,-1){32}}

\put(60,96){\oval(16,16){\makebox(0,0){($$}}}
\put(100,96){\oval(16,16){\makebox(0,0){$E$}}}
\put(140,96){\oval(16,16){\makebox(0,0){$)$}}}

\put(96,90){\line(-1,-1){32}}
\put(100,88){\line(0,-1){28}}
\put(104,90){\line(1,-1){32}}

\put(60,52){\oval(16,16){\makebox(0,0){$E$}}}
\put(100,52){\oval(16,16){\makebox(0,0){$+$}}}
\put(140,52){\oval(16,16){\makebox(0,0){$T$}}}

\put(60,44){\line(0,-1){28}}

\put(60,8){\oval(16,16){\makebox(0,0){$T$}}}

\end{picture}
\end{center}

 \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}

\end{enumerate}


\end{document}
 
