\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma W/Solução do professor\hfill {08/5/2013}

\vspace*{2mm}
\begin{enumerate}

 \item {\footnotesize Prove que $\{x{\tt 1}^n\,|\, n\geq 0, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|=n\}$ não é uma
       linguagem regular.}

       \textit{Solução}: Seja $L$ a linguagem em questão e suponha que ela é regular. Como a classe das linguagens
			 regulares é fechada sob interseção, segue-se que $L\cap \{\tt 0\}^*\{\tt 1\}^*$ é regular. Mas
			 $L\cap \{\tt 0\}^*\{\tt 1\}^*=\{{\tt 0}^k{\tt 1}^n\,|\, k\leq n\}$ e esta não é regular. Contradição! Logo,
			 $L$ é regular.


 \item {\footnotesize Encontre express\~oes regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o n\'umero de {\tt a}s
               mais o de {\tt b}s em $w$ \'e par$\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ cont\'em o s\'{\i}mbolo
              \verb+1+ e $\eta(w) \mbox{ mod } 3=0\}$.  ($\eta(w)$ é o número representado por $w$ na base 2.)
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $c^*((a+b)c^*(a+b)c^*)^*$.
        \item Autômato finito que reconhece a linguagem:

              \begin{picture}(120,30)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

               \node[Nmarks=i, iangle=180](i)(20,5){i}
               \node[Nmarks=r](0)(20,20){0}
               \node(1)(40,20){1}
               \node(2)(60,20){2}

              \drawloop[loopangle=90](i){0}
              \drawedge[curvedepth=-6, ELside=r](i,1){1}
              \drawloop[loopangle=90](0){0}
              \drawedge[curvedepth=3](0,1){1}
              \drawedge[curvedepth=3](1,0){1}
              \drawedge[curvedepth=3](1,2){0}
              \drawedge[curvedepth=3](2,1){0}
              \drawloop[loopangle=90](2){1}
             \end{picture}

       Eliminando-se o estado 2, e depois o estado 1, obtém-se:

             \begin{picture}(120,30)
              \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

              \node[Nmarks=i, iangle=180](i)(20,5){i}
              \node[Nmarks=r](0)(20,20){0}
              \node(1)(40,20){1}

              \drawloop[loopangle=90](i){0}
              \drawedge[curvedepth=-6, ELside=r](i,1){1}
              \drawloop[loopangle=90](0){0}
              \drawedge[curvedepth=3](0,1){1}
              \drawedge[curvedepth=3](1,0){1}
              \drawloop[loopangle=0](1){$01^*0$}

              \node[Nmarks=i, iangle=180](ix)(90,5){i}
              \node[Nmarks=r](0x)(90,20){0}

              \drawloop[loopangle=0](ix){0}
              \drawedge[curvedepth=0](ix,0x){$1(01^*0)^*1$}
              \drawloop[loopangle=0](0x){$0+1(01^*0)^*1$}

             \end{picture}

             Obtém-se, então, a expressão $0^*1(01^*0)^*1(0+1(01^*0)^*1)^*$.
       \end{list}

 \item {\footnotesize Construa gramáticas livres do contexto para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^{2n}{\tt 1}^{3n}\,|\, n\geq 0\}$.
        \item $\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 1\}^2\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w=w^R\}
              \{{\tt 0}^n{\tt 1}^n\,|\,n\geq 1\}^2$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $S\,\rightarrow\, {\tt 00} S {\tt 111} \,|\, \lambda$
        \item $P\,\rightarrow\, AABAA$ \\
       	      $A\,\rightarrow\, {\tt 0} A {\tt 1} \,|\, {\tt 01}$ \\
      	      $B\,\rightarrow\, {\tt 0} B {\tt 0} \,|\, {\tt 1} B {\tt 1} \,|\, {\tt 0}\,|\, {\tt 1}
							              \,|\, \lambda$
       \end{list}

 \item {\footnotesize Seja a gram\'atica:
       \begin{quote}
        $G$: $X \,\rightarrow\, {\tt a}X{\tt b} \,|\, X{\tt b} \,|\, \lambda$
       \end{quote}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ é amb\'{\i}gua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente $G$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G$ é amb\'{\i}gua: a palavra {\tt abb} tem duas derivações mais à esquerda:
				      \begin{itemize}
							 \item $X\,\Rightarrow\,{\tt a}X{\tt b}\,\Rightarrow\,{\tt a}X{\tt bb}\,\Rightarrow\,{\tt abb}$
							 \item $X\,\Rightarrow\,X{\tt b}\,\Rightarrow\,{\tt a}X{\tt bb}\,\Rightarrow\,{\tt abb}$
							\end{itemize}
        \item $X \,\rightarrow\, AB$ \\
				      $A\,\rightarrow {\tt a}A{\tt b} \,|\, \lambda$ \\
							$B\,\rightarrow\, {\tt b}B \,|\, \lambda$
       \end{list}

 \item {\footnotesize Seja a gram\'atica:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, ABC$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A {\tt b} \,|\, \lambda$
	      \item[\ ] $B\,\rightarrow\,{\tt b} B \,|\, {\tt b}$
	      \item[\ ] $C\,\rightarrow\, {\tt b} C {\tt c} \,|\, \lambda$
	     \end{enumerate}
       Obtenha uma GLC equivalente na forma normal de Chomsky. Deixe bem claros todos os passos executados,
			 assim como a ordem em que foram executados, para chegar à gramática final.}

       \textit{Solução}:
			\begin{enumerate}
			 \item[1.] Eliminação de regras $\lambda$: \\
			        Variáveis anuláveis: $\{A,C\}$. Resultado:\\
							\begin{quote}
	             $P\,\rightarrow\, ABC \,|\, AB \,|\, BC \,|\, B$ \\
	             $A\,\rightarrow\,{\tt a} A {\tt b} \,|\, {\tt ab}$ \\
	             $B\,\rightarrow\,{\tt b} B \,|\, {\tt b}$ \\
	             $C\,\rightarrow\, {\tt b} C {\tt c} \,|\, {\tt bc}$
              \end{quote}
			 \item[2.] Eliminação de regras unitárias: \\
			        Variáveis encadeadas: $\mbox{enc}(P)=\{P,B\}$, $\mbox{enc}(X)=\{X\}$ para $X\in\{A,B,C\}$.
							Resultado:
							\begin{quote}
	             $P\,\rightarrow\, ABC \,|\, AB \,|\, BC \,|\, {\tt b}B \,|\, {\tt b}$ \\
	             $A\,\rightarrow\,{\tt a} A {\tt b} \,|\, {\tt ab}$ \\
	             $B\,\rightarrow\,{\tt b} B \,|\, {\tt b}$ \\
	             $C\,\rightarrow\, {\tt b} C {\tt c} \,|\, {\tt bc}$
              \end{quote}
			 \item[3.] Variáveis para lado direito maior que dois:
							\begin{quote}
	             $P\,\rightarrow\, ABC \,|\, AB \,|\, BC \,|\, YB \,|\, {\tt b}$ \\
	             $A\,\rightarrow\, XAY \,|\, XY$ \\
	             $B\,\rightarrow\, YB \,|\, {\tt b}$ \\
	             $C\,\rightarrow\, YCZ \,|\,  YZ$ \\
	             $X\,\rightarrow\, {\tt a}$ \hspace*{1cm} $Y\,\rightarrow\, {\tt b}$ \hspace*{1cm}
	             $Z\,\rightarrow\, {\tt c}$
              \end{quote}
			 \item[4.] Quebrando lado direito maior que dois:
							\begin{quote}
	             $P\,\rightarrow\, AR_1 \,|\, AB \,|\, BC \,|\, YB \,|\, {\tt b}$ \\
	             $A\,\rightarrow\, XR_2 \,|\, XY$ \\
	             $B\,\rightarrow\, YB \,|\, {\tt b}$ \\
	             $C\,\rightarrow\, YR_3 \,|\,  YZ$ \\
	             $X\,\rightarrow\, {\tt a}$ \hspace*{1cm} $Y\,\rightarrow\, {\tt b}$ \hspace*{1cm}
	             $Z\,\rightarrow\, {\tt c}$ \\
	             $R_1\,\rightarrow\, BC$ \hspace*{.4cm} $R_2\,\rightarrow\, AY$ \hspace*{.5cm}
	             $R_3\,\rightarrow\, CZ$
              \end{quote}

			\end{enumerate}
\end{enumerate}

\end{document}
