\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 5/6/2018

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Prove que $\{xx^r \,|\, x\in \{{\tt 0},{\tt 1}\}^*\}$ 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=0^*$ e duas palavras arbitrárias de $R$, ${\tt 0}^i$ e ${\tt 0}^j$, $i\not=j$. Considere-se o sufixo ${\tt 11}{\tt 0}^i$; claramente ${\tt 0}^i{\tt 11}{\tt 0}^i$ pertence à linguagem em questão, e ${\tt 0}^j{\tt 11}{\tt 0}^i$ não pertence. Logo, pelo teorema da invariância à direita, a linguagem não é regular.

 \item {\footnotesize Sejam $L_1=\{{\tt a}^n \,|\, n\geq 1000\}$ (regular), $L_2=\{{\tt a}^n{\tt b}^k \,|\, n\geq k\}$ (não regular) e $L_3=\{{\tt a}^n \,|\, n \mbox{ é número primo}\}$ (não regular). Para cada linguagem a seguir, mostre que ela é regular ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_2-L_1$;
        \item $L_3-L_1$;
        \item $L_1\cap L_3$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Como $L_1\subset L_2$, $(L_2-L_1)\cup L_1=L_2$. Como as linguages regulares são fechadas sob união,
              se $L_2-L_1$ fosse regular, como $L_1$ é regular, então $L_2$ teria que ser regular. Mas $L_2$ não é
              regular. Logo, \textbf{$L_2-L_1$ não é regular}.
				\item $L_3-L_1=\{{\tt 0}^n\,|\, n \mbox{ é primo e } n<1000\}$. Tal linguagem é finita. Logo \textbf{é regular}.
        \item Como $L_3-L_1$ é regular e as linguagens regulares são fechadas sob união, se $L_1\cap L_3$ fosse
				      regular, então $(L_1\cap L_3)\cup(L_3-L_1)=L_3$ seria regular, o que não é o caso. Logo, $L_1\cap L_3$
							\textbf{não é regular}.
       \end{list}

 \item {\footnotesize Construa uma expressão regular que denote a linguagem $$\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w) \mbox{ é par e } n_{\tt b}(w) \mbox{ é par}\}\mbox{.}$$}

       \textit{Solução}:$[c+ac^*a+bc^*b+(ac^*b+bc^*a)(ac^*a+bc^*b)^*(ac^*b+bc^*a)]^*$.

 \item {\footnotesize Construa um APD para a linguagem da questão 1, se possível. Se não for possível, construa APN.}

       \textit{Solução}:
	
       \begin{picture}(66,26)
        \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=6, fillgray=0.9}

        \node[Nmarks=i](1)(20,9){1}
        \node[Nmarks=r](2)(46,9){2}

        \drawedge[curvedepth=0,ELside=r](1,2){$\lambda,\lambda/\lambda$}
        \drawloop[loopangle=90](1){\shortstack{${\tt 0},\lambda/{\tt 0}$ \\ ${\tt 1},\lambda/{\tt 1}$}}
        \drawloop[loopangle=90](2){\shortstack{${\tt 0},{\tt 0}/\lambda$ \\ ${\tt 1},{\tt 1}/\lambda$}}
       \end{picture}

 \item {\footnotesize Construa GLCs que gerem:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^m{\tt b}^n \,|\, m\not=n\}$;
        \item $L_2=\{{\tt a}^{m+n}{\tt b}^{m}{\tt c}^{n} \,|\, m \mbox{ é par e } n \mbox{ é ímpar}\}$;
	      \item $L_1\cup L_2\cup (L_1L_2L_2)^+\cup (L_2L_1L_1)^+$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Para $L_1=\{{\tt a}^m{\tt b}^n \,|\, m\not=n\}$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt a} P {\tt b}\,|\, A \,|\, B$
               \item[\ ] $A\,\rightarrow\, {\tt a} A \,|\, {\tt a}$
               \item[\ ] $B\,\rightarrow\, {\tt b} B \,|\, {\tt b}$
              \end{enumerate}
        \item Para $L_2=\{{\tt a}^{m+n}{\tt b}^{m}{\tt c}^{n} \,|\, m \mbox{ é par e } n \mbox{ é ímpar}\}$:
              \begin{enumerate}
               \item[\ ] $Q\,\rightarrow\, {\tt aa} P {\tt cc}\,|\, {\tt a}X{\tt c}$
               \item[\ ] $X\,\rightarrow\, {\tt aa} X {\tt bb}\,|\, \lambda$
              \end{enumerate}
				\item Para $L_1\cup L_2\cup (L_1L_2L_2)^+\cup (L_2L_1L_1)^+$:
              \begin{enumerate}
               \item[\ ] $R\,\rightarrow\, P \,|\,Q \,|\, S \,|\, T$
               \item[\ ] $S\,\rightarrow\, PQQS \,|\, PQQ$
               \item[\ ] $T\,\rightarrow\, QPPT \,|\, QPP$
							 \item[\ ] mais as regras dos dois ítens anteriores.
              \end{enumerate}
       \end{list}

 \item {\footnotesize Seja a gramática $G$ com as regras:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, A \,|\, B$
        \item[\ ] $A\,\rightarrow\, {\tt a}A{\tt a} \,|\, \lambda$
        \item[\ ] $B\,\rightarrow\, {\tt b}B{\tt bb} \,|\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ é ambígua.
        \item Remova a ambiguidade de $G$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Duas DMEs para $\lambda$:
              \begin{enumerate}
               \item[\ ] $P\,\Rightarrow\, A \,\Rightarrow\, \lambda$
               \item[\ ] $P\,\Rightarrow\, B \,\Rightarrow\, \lambda$
              \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A \,|\, B \,|\, \lambda$
               \item[\ ] $A\,\rightarrow\, {\tt a}A{\tt a} \,|\, {\tt aa}$
               \item[\ ] $B\,\rightarrow\, {\tt b}B{\tt bb} \,|\, {\tt bbb}$
              \end{enumerate}
       \end{list}

 \item {\footnotesize (4 pontos) Seja a gramática:
       \begin{enumerate}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
	      \item[\ ] $P\,\rightarrow\, A A A  \,|\,  B$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, B \,|\, BC$
	      \item[\ ] $B\,\rightarrow\,\lambda$
	      \item[\ ] $C\,\rightarrow\, BC$
	     \end{enumerate}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Se existirem símbolos inúteis, elimine-os.
        \item Elimine regras $\lambda$.
        \item Elimine variáveis inúteis.
        \item Elimine regras unitárias.
        \item Obtenha uma GLC equivalente na forma normal de Chomsky.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $V'=\{B,P,A\}$. Eliminando-se $C$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A A A  \,|\,  B$
	             \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, B$
	             \item[\ ] $B\,\rightarrow\,\lambda$
							\end{enumerate}
        \item $\textit{VA}=\{B,P,A\}$. Obtém-se:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A A A \,|\, A A \,|\, A \,|\, B$
	             \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, {\tt a} \,|\, B$
							\end{enumerate}
        \item Como $B$ é inútil:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A A A \,|\, A A \,|\, A$
	             \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, {\tt a}$
							\end{enumerate}
        \item Como $\textit{enc}(P)=\{P,A\}$ e $\textit{enc}(A)=\{A\}$: 
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A A A \,|\, A A \,|\, {\tt a}A \,|\, {\tt a}$
	             \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, {\tt a}$
							\end{enumerate}
        \item GLC equivalente na forma normal de Chomsky:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, AB \,|\, A A \,|\, XA \,|\, {\tt a}$
	             \item[\ ] $A\,\rightarrow\,XA \,|\, {\tt a}$
	             \item[\ ] $B\,\rightarrow\,AA$
	             \item[\ ] $X\,\rightarrow\,{\tt a}$
							\end{enumerate}
       \end{list}
\end{enumerate}

\end{document}
