\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{amsfonts}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2016 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent \textbf{Segunda Prova}/Solução do professor  \hfill 19/5/2016

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

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_2-L_1=\{{\tt 0}^n \,|\, \mbox{$n$ é número primo e } n<1000\}$. Tal conjunto é finito, logo
				      é regular.
        \item $L_1\cap L_2=\{{\tt 0}^n \,|\, \mbox{$n$ é número primo e } n\geq 1000\}$. Suponha que tal
				      conjunto seja regular. Como as linguagens regulares são fechadas sob união, a linguagem
							$(L_1\cap L_2)\cup(L_2-L_1)$ deve ser regular. Mas $(L_1\cap L_2)\cup(L_2-L_1)=L_2$, que não
							é regular, Portanto, $L_1\cap L_2$ não é regular.
       \end{list}
 \item {\footnotesize Obtenha expressões regulares que denotem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ inicia com {\tt 0} e } |w| \mbox{ é par}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w|>0 \mbox{ e } w \mbox{ tem um único {\tt 0} nas posições ímpares}\}$.
				      Exemplos, sublinhando o zero na posição ímpar: \underline{\tt 0}, \underline{\tt 0}{\tt 0},
							\underline{\tt 0}{\tt 1}, \underline{\tt 0}{\tt 01}, \underline{\tt 0}{\tt 11}, {\tt 10}\underline{\tt 0},
							{\tt 11}\underline{\tt 0}, \underline{\tt 0}{\tt 010} etc.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $0(0+1)((0+1)(0+1))^*$.
        \item $(1(0+1))^*0((0+1)1)^*(\lambda+0+1)$.
       \end{list}

 \item {\footnotesize Construa:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um APD que reconheça $\{{\tt a}^n({\tt cba})^n\,|\, n\in\mathbb{N}\}$.
				\item Um APN que reconheça $\{{\tt a}^n({\tt abc})^n\,|\, n\in\mathbb{N}\}$.
        \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um APD para $\{{\tt a}^n({\tt cba})^n\,|\, n\in\mathbb{N}\}$:

               \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(100,21)\setlength{\unitlength}{1mm}
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=4}

                 \node[Nmarks=ir,iangle=180](2)(20,7.5){}
                 \node[Nmarks=r](3)(45,7.5){}

                 \drawloop[loopangle=90](2){${\tt a},\lambda/{\tt C}$}
                 \drawedge[curvedepth=0](2,3){${\tt c},{\tt C}/{\tt B}$}
                 \drawloop[loopangle=0](3){\shortstack{${\tt a},{\tt A}/\lambda$ \\
								             ${\tt b},{\tt B}/{\tt A}$ \\ ${\tt c},{\tt C}/{\tt B}$}}
                \end{picture}
               }
        \item Um APN para $\{{\tt a}^n({\tt abc})^n\,|\, n\in\mathbb{N}\}$:

               \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(100,21)\setlength{\unitlength}{1mm}
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=4}

                 \node[Nmarks=ir,iangle=180](2)(20,7.5){}
                 \node[Nmarks=r](3)(45,7.5){}

                 \drawloop[loopangle=90](2){${\tt a},\lambda/{\tt A}$}
                 \drawedge[curvedepth=0](2,3){${\tt a},{\tt A}/{\tt B}$}
                 \drawloop[loopangle=0](3){\shortstack{${\tt a},{\tt A}/{\tt B}$ \\
								             ${\tt b},{\tt B}/{\tt C}$ \\ ${\tt c},{\tt C}/\lambda$}}
                \end{picture}
               }
        \end{list}

 \item {\footnotesize Construa GLCs para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{x{\tt b}y\,|\, x,y\in \{{\tt a},{\tt b}\}^* \mbox{ e } |x|=|y|\}$.
        \item $\{{\tt a}^m{\tt b}^k{\tt c}^n\,|\,k>m+n\}$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item GLC para $\{x{\tt b}y\,|\, x,y\in \{{\tt a},{\tt b}\}^* \mbox{ e } |x|=|y|\}$:
				      \begin{quote}
							 $P \,\rightarrow\, XPX \,|\, {\tt b}$ \\
							 $X \,\rightarrow\, {\tt a} \,|\, {\tt b}$
							\end{quote}
        \item GLC para $\{{\tt a}^m{\tt b}^k{\tt c}^n\,|\,k>m+n\}$:
				      \begin{quote}
							 $P \,\rightarrow\, ABC$ \\
							 $A \,\rightarrow\, {\tt a}A{\tt b} \,|\, \lambda$ \\
							 $B \,\rightarrow\, {\tt b}B \,|\, {\tt b}$ \\
							 $C \,\rightarrow\, {\tt b}C{\tt c} \,|\, \lambda$
							\end{quote}
       \end{list}

 \item {\footnotesize Mostre que a gramática a seguir é ambígua:
       \begin{quote}
        $A\,\rightarrow\, {\tt 0}A{\tt 1} \,|\, B$ \\
        $B\,\rightarrow\, {\tt 0}B{\tt 11} \,|\, C$ \\
        $C\,\rightarrow\, {\tt 0}C{\tt 111} \,|\, \lambda$
       \end{quote}}

       \textit{Solução}:

       Duas DMEs para {\tt 001111}:
			 \begin{quote}
			  $A\Rightarrow{\tt 0}A{\tt 1}\Rightarrow{\tt 0}B{\tt 1}\Rightarrow{\tt 0}C{\tt 1}
				    \Rightarrow{\tt 00}C{\tt 1111}\Rightarrow{\tt 001111}$ \\
			  $A\Rightarrow B\Rightarrow{\tt 0}B{\tt 11}\Rightarrow{\tt 00}B{\tt 1111}
				    \Rightarrow{\tt 00}C{\tt 1111}\Rightarrow{\tt 001111}$
			 \end{quote}
 \item {\footnotesize Transforme a GLC a seguir em uma equivalente na forma normal de Chomsky.
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, {\tt a}P{\tt b}  \,|\, A$
	      \item[\ ] $A\,\rightarrow\, B{\tt a}B \,|\, {\tt a}B$
	      \item[\ ] $B\,\rightarrow\, {\tt a}B{\tt c} \,|\, \lambda$
	     \end{enumerate}
			 Primeiro elimine regras $\lambda$, depois unitárias, etc., como preconiza o método visto.}

       \textit{Solução}:

       \begin{enumerate}
			  \item Como \textit{VA}$=\{B\}$, ao eliminar regras $\lambda$ obtém-se:
	            \begin{quote}
	             $P\,\rightarrow\, {\tt a}P{\tt b}  \,|\, A$ \\
	             $A\,\rightarrow\, B{\tt a}B \,|\, {\tt a}B \,|\, B{\tt a} \,|\, {\tt a}$ \\
	             $B\,\rightarrow\, {\tt a}B{\tt c} \,|\, {\tt ac}$
	            \end{quote}
			  \item Como \textit{enc}$(P)=\{P,A\}$, \textit{enc}$(A)=\{A\}$ e \textit{enc}$(B)=\{B\}$,
				      ao eliminar regras unitárias obtém-se:
	            \begin{quote}
	             $P\,\rightarrow\, {\tt a}P{\tt b}\,|\, B{\tt a}B \,|\, {\tt a}B \,|\, B{\tt a} \,|\, {\tt a}$ \\
	             $A\,\rightarrow\, B{\tt a}B \,|\, {\tt a}B \,|\, B{\tt a} \,|\, {\tt a}$ \\
	             $B\,\rightarrow\, {\tt a}B{\tt c} \,|\, {\tt ac}$
	            \end{quote}
			  \item Como $A$ é inútil:
	            \begin{quote}
	             $P\,\rightarrow\, {\tt a}P{\tt b}\,|\, B{\tt a}B \,|\, {\tt a}B \,|\, B{\tt a} \,|\, {\tt a}$ \\
	             $B\,\rightarrow\, {\tt a}B{\tt c} \,|\, {\tt ac}$
	            \end{quote}
			  \item Terminais por variáveis em regras com lado direito maior do que um:
	            \begin{quote}
	             $P\,\rightarrow\, XPY\,|\, BXB \,|\, XB \,|\, BX \,|\, {\tt a}$ \\
	             $B\,\rightarrow\, XBZ \,|\, XZ$ \\
	             $X\,\rightarrow\, {\tt a}$ \\
	             $Y\,\rightarrow\, {\tt b}$ \\
	             $Z\,\rightarrow\, {\tt c}$
	            \end{quote}
			  \item Quebrando lado direito maior do que dois:
	            \begin{quote}
	             $P\,\rightarrow\, XR_1\,|\, BR_2 \,|\, XB \,|\, BX \,|\, {\tt a}$ \\
	             $B\,\rightarrow\, XR_3 \,|\, XZ$ \\
	             $X\,\rightarrow\, {\tt a}$ \\
	             $Y\,\rightarrow\, {\tt b}$ \\
	             $Z\,\rightarrow\, {\tt c}$ \\
	             $R_1\,\rightarrow\, PY$ \\
	             $R_2\,\rightarrow\, XB$ \\
	             $R_3\,\rightarrow\, BZ$
	            \end{quote}
			 \end{enumerate}
\end{enumerate}

\end{document}