\documentclass[11pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
%\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage         {amsfonts}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2018 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Segunda Prova}/Solução do professor \hfill 23/10/2018 \hfill Valor: 23 pontos

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Prove que $\{{\tt 0}^nx{\tt 0}^n\,|\, x\in\{{\tt 1}\}^* \mbox{ e } n\in\mathbb{N}\}$ não é linguagem regular usando o teorema da invariância à direita ou o lema do bombeamento.}

       \textit{Solução}:

       Pelo teorema da invariância à direita. Seja $R=\{{\tt 0}\}^*$. Sejam ${\tt 0}^i$ e ${\tt 0}^j$, $i\not=j$, palavras arbitrárias de $R$. Como ${\tt 0}^i{\tt 1}{\tt 0}^i$ pertence à linguagem e ${\tt 0}^j{\tt 1}{\tt 0}^i$ não pertence, segue-se, pelo teorema da invariância à direita, que a linguagem não é regular.
 \item {\footnotesize Seja $L_1$ uma linguagem \emph{não livre do contexto}. Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item se $L_2$ é uma linguagem finita, $L_1-L_2$ não é livre do contexto;
        \item se $L_2$ é uma linguagem regular, $L_1-L_2$ pode ser regular.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Se $L_2$ é uma linguagem finita, $L_1\cap L_2$ também é finita e, portanto, regular.
				      Com isto, se $L_1-L_2$ for livre do contexto, então $(L_1-L_2)\cup(L_1\cap L_2)$ tem que ser livre do contexto. Mas $(L_1-L_2)\cup(L_1\cap L_2)=L_1$, que não é livre do contexto. Logo, $L_1-L_2$ não pode ser livre do contexto se $L_1$ não for.
        \item Sim, se $L_2$ é uma linguagem regular, $L_1-L_2$ pode ser regular. Exemplo: para $L_2=\Sigma^*$, $L_1-L_2=\emptyset$.
       \end{list}
 \item {\footnotesize Encontre expressões regulares que denotem os conjuntos:
         \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém {\tt aba}$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém exatamente um {\tt aba}$\}$.
         \end{list}}

       \textit{Solução}:

         \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
          \item $(a+b)^*aba(a+b)^*$;
          \item $(b+a^+bb)^*a^+ba(a+bb)^*(\lambda+b)$.
         \end{list}
 \item {\footnotesize Construa uma GLC que gere e um AP que reconheça $\{{\tt 0}^nx{\tt 0}^n\,|\, x\in\{{\tt 1}\}^* \mbox{ e } n\in\mathbb{N}\}$.}

       \textit{Solução}:

         \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
          \item GLC:
					
					      $P\,\rightarrow\,{\tt 0}P{\tt 0}\,|\, X$ \\
					      $X\,\rightarrow\,{\tt 1}X\,|\, \lambda$ \\
          \item AP:
					
                \mbox{\setlength{\unitlength}{1mm}
                 \begin{picture}(100,26)\setlength{\unitlength}{1mm}
                   \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

                   \node[Nmarks=i](0)(20,7.5){}
                   \node(1)(45,7.5){}
                   \node[Nmarks=r](2)(70,7.5){}

                   \drawedge(0,1){$\lambda,\lambda/\lambda$}
                   \drawedge(1,2){$\lambda,\lambda/\lambda$}
  
                   \drawloop[loopangle=90](0){${\tt 0},\lambda/{\tt X}$}
                   \drawloop[loopangle=90](1){${\tt 1},\lambda/\lambda$}
                   \drawloop[loopangle=90](2){${\tt 0},{\tt X}/\lambda$}
            
									\end{picture}
                  }
         \end{list}
    

 \item {\footnotesize Crie GLCs para:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^m{\tt b}^{2m+n}{\tt c}^{3n}\,|\,m,n\in\mathbb{N}\}$;
        \item $L_2=\{xy\in\{{\tt 0},{\tt 1}\}^*\,|\, |x|=|y| \mbox{ e } x\not=y^R\}$;
        \item $(L_1L_2)^+\cup (L_2L_1)^*$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $X\,\rightarrow\,AB$ \\
              $A\,\rightarrow\,{\tt a}A{\tt bb}\,|\,\lambda$ \\
              $B\,\rightarrow\,{\tt b}A{\tt ccc}\,|\,\lambda$
        \item $Y\,\rightarrow\,{\tt 0}Y{\tt 0}\,|\,{\tt 1}Y{\tt 1}\,|\,{\tt 0}C{\tt 1}\,|\,{\tt 1}C{\tt 0}$ \\
              $C\,\rightarrow\,{\tt 0}C\,|\,{\tt 1}C\,|\,\lambda$

        \item $P\,\rightarrow\,R\,|\,S$ \\
              $R\,\rightarrow\,XYR\,|\,XY$ \\
              $S\,\rightarrow\,YXS\,|\,\lambda$ \\
              mais as regras de (a) e (b).
       \end{list}
 \item {\footnotesize Seja a GLC:
      \begin{enumerate}
       \item[\ ] $X\,\rightarrow\, {\tt 0}X\,|\,{\tt 0}X{\tt 1}\,|\,\lambda$
      \end{enumerate}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Mostre que essa GLC é ambígua;
        \item encontre uma GLC não ambígua equivalente.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Duas DME para {\tt 001}:
				      \begin{quote}
							 $X\,\Rightarrow\,{\tt 0}X\,\Rightarrow\,{\tt 00}X{\tt 1}\,\Rightarrow {\tt 001}$ \\
							 $X\,\Rightarrow\,{\tt 0}X{\tt 1}\,\Rightarrow\,{\tt 00}X{\tt 1}\,\Rightarrow {\tt 001}$
							\end{quote}
        \item GLC não ambígua equivalente:

              $X\,\rightarrow\,{\tt 0}X\,|\,Y$ \\
              $Y\,\rightarrow\,{\tt 0}X{\tt 1}\,|\,\lambda$

       \end{list}
 \item {\footnotesize Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ]$S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1}$
        \item[\ ]$A \,\rightarrow\, {\tt 0}A{\tt 0} \,|\, \lambda$
       \end{enumerate}
       Obtenha GLCs equivalentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item na forma normal de Chomsky;
        \item na forma normal de Greibach.
       \end{list}}

       \textit{Solução}:

       Eliminando regras $\lambda$:
			 \begin{quote}
         $S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1} \,|\, {\tt 11}$ \\
         $A \,\rightarrow\, {\tt 0}A{\tt 0} \,|\, {\tt 00}$
			 \end{quote}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Na forma normal de Chomsky:
			 \begin{quote}
         $S \,\rightarrow\, ZX \,|\, UY \,|\, UU$ \\
         $X \,\rightarrow\, SZ$ \\
         $Z \,\rightarrow\, {\tt 0}$ \\
         $Y \,\rightarrow\, AU$ \\
         $U \,\rightarrow\, {\tt 1}$ \\
         $A \,\rightarrow\, ZW \,|\, ZZ$ \\
         $W \,\rightarrow\, AZ$
			 \end{quote}
        \item Na forma normal de Greibach:
			 \begin{quote}
         $S \,\rightarrow\, {\tt 0}SZ \,|\, {\tt 1}AU \,|\, {\tt 1}U$ \\
         $A \,\rightarrow\, {\tt 0}AZ \,|\, {\tt 0}Z$ \\
         $Z \,\rightarrow\, {\tt 0}$ \\
         $U \,\rightarrow\, {\tt 1}$
			 \end{quote}
       \end{list}

\end{enumerate}

\end{document}
