\documentclass[11pt, 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 2015 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\it Segunda Prova} --- Turma N/Solução do professor \hfill 19/5/2015

\begin{enumerate}
 \item {\footnotesize Prove que os seguintes conjuntos não são linguagens regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^n{\tt b}^k\,|\, n>k\}$ \\ $\!\!\Rightarrow$\ use o lema do bombeamento.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ tem mais {\tt a}s que {\tt b}s}\}\{{\tt c}\}^*$ \\
				      $\Rightarrow$\ use o resultado anterior e propriedades de fechamento.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja $L=\{{\tt a}^n{\tt b}^k\,|\, n>k\}$. Suponha que $L$ seja regular e seja $k$ a contante do lema
				      do bombeamento. Seja $z={\tt a}^{k+1}{\tt b}^k$. Como $z\in L$ e $|z|>k$, o lema diz que existem $u$,
							$v$ e $w$ tais que $z=uvw$, $|uv|\leq k$, $v\not=\lambda$ e $uv^iw\in L$ para todo $i\in\mathbb{N}$.
							Seja, então, $u$, $v$ e $w$ tais que $z=uvw$, $|uv|\leq k$ e $v\not=\lambda$. Neste caso,
							$uv^0w={\tt a}^{k+1-|v|}{\tt b}^k$. Como $k+1-|v|\leq k$, $uv^0w\not\in L$, o que contradiz o lema do
							bombeamento. Portanto, L não é regular.
        \item Seja $L=\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ tem mais {\tt a}s que {\tt b}s}\}\{{\tt c}\}^*$.
				      Supondo que $L$ seja regular, como $\{{\tt a}\}^*\{{\tt b}\}^*$ é regular e as linguagens regulares são
							fechadas sob interseção, conclui-se que $L\cap \{{\tt a}\}^*\{{\tt b}\}^*$ é regular. Mas
							$L\cap\{{\tt a}\}^*\{{\tt b}\}^*=\{{\tt a}^n{\tt b}^k\,|\, n>k\}$. Mas esta última não é regular. Logo,
							$L$ não é regular.
       \end{list}

 \item {\footnotesize Obtenha ERs que denotem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ tem um número par de {\tt 0}s antes de seu primeiro {\tt 1}}\}\cup\{{\tt 0}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não contém a subpalavra {\tt 010}}\}$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(00)^*1(0+1)^*+0^*$.
        \item Um AF que reconhece $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não contém a subpalavra {\tt 010}}\}$:
				
              \mbox{\setlength{\unitlength}{1mm}
				       \begin{picture}(120,38)
                \gasset{Nw=6, Nh=6, Nmr=6, fillcolor=Gray, fillgray=0.9, loopdiam=4}

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

                \drawloop[loopangle=90](1){\tt 1}
                \drawedge[curvedepth=0](1,2){\tt 0}
                \drawloop[loopangle=90](2){\tt 0}
                \drawedge[curvedepth=0](2,3){\tt 1}
                \drawedge[curvedepth=-12,ELside=r](3,1){\tt 1}
                \drawedge[curvedepth=-4,ELside=r](1,f){$\lambda$}
                \drawedge[curvedepth=0](2,f){$\lambda$}
                \drawedge[curvedepth=4](3,f){$\lambda$}
               \end{picture}
              }

				Eliminando-se 3 e 2, nesta ordem, obtém-se a ER $(1+00^*11)^*(\lambda+00^*(\lambda+1))$.
       \end{list}

 \item {\footnotesize Construa um APD com reconhecimento padrão (estado final \underline{e} pilha vazia) que reconheça
       a linguagem $\{{\tt a}^n{\tt b}^k\,|\, n>k\}\{{\tt c}\}^+$, caso seja possível. Se não for possível, faça um APN.}

       \textit{Solução}:

              \mbox{\setlength{\unitlength}{1mm}
				       \begin{picture}(120,40)
                \gasset{Nw=6, Nh=6, Nmr=6, fillcolor=Gray, fillgray=0.9, loopdiam=4}

                \node[Nmarks=i, iangle=180](1)(20,35){}
                \node(2)(45,35){}
                \node(3)(57.5,15){}
                \node(4)(70,35){}
                \node[Nmarks=r](5)(95,35){}

                \drawedge[curvedepth=0](1,2){$\lambda$,$\lambda$/F}
                \drawloop[loopangle=90](2){\tt a,$\lambda$/X}
                \drawedge[curvedepth=0,ELside=r](2,3){\tt b,X/$\lambda$}
                \drawedge[curvedepth=0](2,4){\tt c,X/$\lambda$}
%                \drawedge[curvedepth=0](2,5){\tt c,F/$\lambda$}
                \drawloop[loopangle=270](3){\tt b,X/$\lambda$}
%                \drawedge[curvedepth=0](3,5){\tt c,F/$\lambda$}
                \drawedge[curvedepth=0,ELside=r](3,4){\tt c,X/$\lambda$}
                \drawloop[loopangle=90](4){\tt $\lambda$,X/$\lambda$}
                \drawedge[curvedepth=0](4,5){\tt $\lambda$,F/$\lambda$}
                \drawloop[loopangle=90](5){\tt c,$\lambda$/$\lambda$}
               \end{picture}
              }

 \item {\footnotesize Construa GLCs para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in \{{\tt 0},{\tt 1},\#\}^*\,|\,w \mbox{ não contém {\tt 00}, {\tt 01}, {\tt 10}, nem {\tt 11}}\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,k>m+n\}$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P \,\rightarrow\, \#P \,|\, {\tt 0}X \,|\, {\tt 1}X \,|\, \lambda$ \\
				      $X \,\rightarrow\, \#P \,|\, \lambda$
        \item $A \,\rightarrow\, {\tt a}A{\tt c} \,|\, B$ \\
              $B \,\rightarrow\, {\tt b}B{\tt c} \,|\, C$ \\
				      $C \,\rightarrow\, {\tt c}C \,|\, {\tt c}$
       \end{list}

 \item {\footnotesize Seja a gramática $G$ de regras $X \,\rightarrow\, XX \,|\, {\tt 0} \,|\, {\tt 1}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ é ambígua.
        \item Construa uma gramática não ambígua equivalente a $G$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Duas DMEs para {\tt 000}:
				      \begin{quote}
							 $X \,\Rightarrow\, XX \,\Rightarrow\, {\tt 0}X \,\Rightarrow\, {\tt 0}XX \,\Rightarrow\, {\tt 00}X
							          \,\Rightarrow\, {\tt 000}$ \\
							 $X \,\Rightarrow\, XX \,\Rightarrow\, XXX \,\Rightarrow\, {\tt 0}XX \,\Rightarrow\, {\tt 00}X
							          \,\Rightarrow\, {\tt 000}$
							\end{quote}
        \item $X \,\rightarrow\, {\tt 0}X \,|\, {\tt 1}X \,|\, {\tt 0} \,|\, {\tt 1}$
       \end{list}

 \item {\footnotesize Transforme a GLC a seguir em uma equivalente na forma normal de Chomsky.
	     \begin{enumerate}
	      \item[\ ] $F\,\rightarrow\, FTC  \,|\, CD$
	      \item[\ ] $T\,\rightarrow\, TC \,|\, \lambda$
	      \item[\ ] $C\,\rightarrow\, CD \,|\, D$
	      \item[\ ] $D\,\rightarrow\, {\tt a}D{\tt b} \,|\, \lambda$
	     \end{enumerate}
			 Explicite os passos necessários para a transformação, como visto nas aulas.}

       \textit{Solução}:
       \begin{itemize}
			  \item Eliminação de regras $\lambda$.
				
				      Variáveis anuláveis: $\{T,D,C,F\}$. GLC resultante:
	     \begin{enumerate}
	      \item[\ ] $F\,\rightarrow\, FTC \,|\, TC \,|\, FC \,|\, FT \,|\, T \,|\, C \,|\, CD \,|\, D \,|\, \lambda$
	      \item[\ ] $T\,\rightarrow\, TC \,|\, C$
	      \item[\ ] $C\,\rightarrow\, CD \,|\, D$
	      \item[\ ] $D\,\rightarrow\, {\tt a}D{\tt b} \,|\, {\tt ab}$
	     \end{enumerate}              
			  \item Eliminação de regras unitárias.
				
				      enc$(F)=\{F,T,C,D\}$; enc$(T)=\{T,C,D\}$; enc$(C)=\{C,D\}$; enc$(D)=\{D\}$. GLC resultante:
	     \begin{enumerate}
	      \item[\ ] $F\,\rightarrow\, FTC \,|\, TC \,|\, FC \,|\, FT \,|\, CD \,|\, {\tt a}D{\tt b} \,|\, {\tt ab} \,|\, \lambda$
	      \item[\ ] $T\,\rightarrow\, TC \,|\, CD \,|\, {\tt a}D{\tt b} \,|\, {\tt ab}$
	      \item[\ ] $C\,\rightarrow\, CD \,|\, {\tt a}D{\tt b} \,|\, {\tt ab}$
	      \item[\ ] $D\,\rightarrow\, {\tt a}D{\tt b} \,|\, {\tt ab}$
	     \end{enumerate}              
			  \item Introdução de novas variáveis.  GLC resultante:
				
	     \begin{enumerate}
	      \item[\ ] $F\,\rightarrow\, FTC \,|\, TC \,|\, FC \,|\, FT  \,|\, CD \,|\, ADB \,|\, AB \,|\, \lambda$
	      \item[\ ] $T\,\rightarrow\, TC \,|\, CD \,|\, ADB \,|\, AB$
	      \item[\ ] $C\,\rightarrow\, CD \,|\, ADB \,|\, AB$
	      \item[\ ] $D\,\rightarrow\, ADB \,|\, AB$
	      \item[\ ] $A\,\rightarrow\, {\tt a}$
	      \item[\ ] $B\,\rightarrow\, {\tt b}$
	     \end{enumerate}              
			  \item Quebrando regras.  GLC resultante:
				
	     \begin{enumerate}
	      \item[\ ] $F\,\rightarrow\, FX \,|\, TC \,|\, FC \,|\, FT \,|\, CD \,|\, AY \,|\, AB \,|\, \lambda$
	      \item[\ ] $T\,\rightarrow\, TC \,|\, CD \,|\, AY \,|\, AB$
	      \item[\ ] $C\,\rightarrow\, CD \,|\, AY \,|\, AB$
	      \item[\ ] $D\,\rightarrow\, AY \,|\, AB$
	      \item[\ ] $A\,\rightarrow\, {\tt a}$
	      \item[\ ] $B\,\rightarrow\, {\tt b}$
	      \item[\ ] $X\,\rightarrow\, TC$
	      \item[\ ] $Y\,\rightarrow\, DB$
	     \end{enumerate}              
			 \end{itemize}
\end{enumerate}
\end{document}