\documentclass[11pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\vspace*{20mm}
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}/DINTER
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Segunda Prova} \hfill 29/10/2010

\vspace*{2mm}
\textbf{Faça 12 questões dentre as seguintes.}
\vspace*{2mm}
\begin{enumerate}

 \item Construa APDs que reconheçam as linguagens:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\verb+0+^{3n}\verb+1+^{2n}\,|\,n\geq 0\}$
          \item $\{\verb+0+^m\verb+1+^n\,|\,m<n\}$
          \end{list}

 \item Construa um APD que reconhe\c ca toda palavra com par\^enteses balanceados. 
       Exemplos de palavras da linguagem: $\lambda$, \verb+()+, \verb+(())()+. Exemplos de
       palavras que n\~ao pertencem \`a linguagem: \verb+(+, \verb+)(+, \verb+())+.

       Generalize para o caso em que existem $n$ tipos de par\^enteses. Neste caso, considere que
       cada ocorr\^encia de um abre par\^enteses, $a_i$, tem de ser seguida \`a direita por uma
       ocorr\^encia do fecha par\^enteses respectivo, $b_i$, sendo que entre $a_i$ e $b_i$ s\'o
       pode ocorrer uma palavra com par\^enteses balanceados. Se $i=2$, $a_1=\verb+(+$,
       $b_1=\verb+)+$, $a_2=\verb+[+$, $b_2=\verb+]+$, seriam exemplos de palavras da linguagem:
       $\lambda$, \verb+()+, \verb+[()]()+, \verb+[[()]()]([])+. Exemplos de palavras que n\~ao
       pertencem \`a linguagem: \verb+(+, \verb+][+, \verb+()]+, \verb+(]+, \verb+([)]+.

 \item Construa APNs 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+^n\,|\,n\geq 0\}\cup\{\verb+0+^n\verb+1+^{2n}\,\,|\,\,
              n\geq 0\}$
        \item $\{\verb+0+^n\verb+1+^k\,|\,n\leq k\leq 2n\}$
       \end{list}

 \item Construa GLCs para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^{3m+2n+1} \,|\, m,n\geq 0\}$
        \item $\{\verb+a+^n\verb+b+^{2n+k}\verb+c+^{3k} \,|\, n,k\geq 0\}$
	      \item $\{\verb+a+^m\verb+b+^n\verb+c+^k \,|\, n>m+k\}$
       \end{list}

 \item Construa GLCs 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 Construa uma gram\'atica sem regras $\lambda$ equivalente \`a seguinte:
       \begin{quote}
	      \begin{tabular}{ccl}
	        $P$ & $\rightarrow$ & $B P A \,|\, A$ \\
	        $A$ & $\rightarrow$ & $\verb+a+ A \,|\, B \,|\, \lambda$ \\
	        $B$ & $\rightarrow$ & $B \verb+b+ \verb+a+ \,|\, \lambda$
	      \end{tabular}
	     \end{quote}

 \item Seja a gram\'atica $G$:
	\begin{quote}
	\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{quote}
	\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 Seja $G$ uma gram\'{a}tica e $w\in L(G)$, de tamanho $n$. Para os casos em que $G$ est\'a
        na forma normal de Chomsky e em que est\'a na forma normal de Greibach, determine:
      	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	       \item O tamanho de uma deriva\c{c}\~{a}o de $w$.
	       \item A profundidade m\'{a}xima de uma AD de $w$.
	       \item A profundidade m\'{\i}nima de uma AD de $w$.
	      \end{list}

 \item  Use o lema do bombeamento para mostrar que
	as seguintes linguagens n\~{a}o s\~{a}o livres do contexto:
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item $\{\verb+a+^{n^2} \,\,|\,\, n\geq 0\}$
	 \item $\{\verb+a+^n\verb+b+^{2n}\verb+a+^n \,\,|\,\, n\geq 0\}$
	\end{list}

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

 \item Construa um AP para $L_1=\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ $w$ tem mais
       \verb+1+'s que \verb+0+'s$\}$. Construa um AFD para $L_2=\{w\in\{\verb+0+,\verb+1+\}^*
       \,|\,$ $|w|\geq 2$ e o pen\'ultimo s\'{\i}mbolo de $w$ \'e \verb+1+$\}$. Usando o
       m\'etodo da prova do Teorema 29 construa um AP para $L_1\cap L_2$.

 \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 Um aut\^omato de duas pilhas \'e uma s\^extupla $M=(E,\Sigma,\Gamma,\delta,I,F)$, em que:
       \begin{itemize}
        \item $E$, $\Sigma$, $\Gamma$,$I$ e $F$ s\~ao como em APNs; e
        \item $\delta$ \'e uma fun\c c\~ao de $E\times(\Sigma\cup\{\lambda\})\times(\Gamma\cup
              \{\lambda\})\times(\Gamma\cup\{\lambda\})$ para $D$, onde $D$ \'e constitu\'{\i}do dos
              subconjuntos finitos de $E\times\Gamma^*\times\Gamma^*$.
       \end{itemize}
       Uma transi\c c\~ao neste tipo de aut\^omato manipula duas pilhas simultaneamente. Assim, a
       transi\c c\~ao $[e',z_1,z_2]\in\delta(e,a,A_1,A_2)$, que pode ser representada em um diagrama
       de estados por:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,20)
         \gasset{Nw=8, Nh=8, Nmr=4, loopdiam=6}

         \node(e)(20,10){$e$}
         \node(el)(70,10){$e'$}

         \drawedge(e,el){$a,A_1/z_1,A_2/z_2$}
        \end{picture}
       }

      significa, no caso em que nenhuma das entidades envolvidas \'e $\lambda$, que ``estando no
      estado $e$, se o pr\'oximo s\'{\i}mbolo de entrada for $a$, o s\'{\i}mbolo no topo da pilha 1
      for $A_1$ e o s\'{\i}mbolo no topo da pilha 2 for $A_2$, h\'a uma transi\c c\~ao para o estado
      $e'$, $A_1$ \'e desempilhado e $z_1$ \'e empilhado na pilha 1, e $A_2$ \'e desempilhado e
      $z_2$ \'e empilhado na pilha 2.
      Fa\c ca aut\^omatos a duas pilhas que reconhe\c cam:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item $\{\verb+a+^n\verb+b+^n\verb+c+^n\,\,|\,\,n\geq 0\}$
       \item $\{\verb+a+^n\verb+b+^n\verb+c+^n\verb+d+^n\,\,|\,\,n\geq 0\}$
      \end{list}

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