\documentclass[11pt]{report}

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

\newcounter{conta}
\usepackage{comment}
\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 2017 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Segunda Lista de Exercícios}/Solução do professor \hfill Data de entrega: 31/10/2017 \hfill Valor: 10 pontos

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Usando o teorema da invariância à direita, mostre que os seguintes conjuntos não são linguagens regulares:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{x{\tt 1}^n\,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|\leq n\}$;
        \item $\{{\tt 0}^m{\tt 1}^n\,|\, m>2n\}$;
        \item $\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(w)=n_{\tt 1}(w)\}$;
        \item $\{xx \,|\, x\in \{{\tt 0},{\tt 1}\}^*\}$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Seja $L=\{x{\tt 1}^n\,|\, x\in\{{\tt 0},{\tt 1}\}^*|x|\leq n\}$. Seja $R=\{{\tt 0}\}^*$ e sejam
					    ${\tt 0}^i,{\tt 0}^j\in R$, $i<j$, palavras arbitrárias de $R$. Segue-se que ${\tt 0}^i{\tt 1}^i\in L$ e
							${\tt 0}^j{\tt 1}^i\not\in L$. Portanto, $L$ não é regular.
        \item Seja $L=\{{\tt 0}^m{\tt 1}^n\,|\, m>2n\}$. Seja $R=\{{\tt 0}\}^*$. Sejam
				      ${\tt 0}^i,{\tt 0}^j\in R$, $i<j$, duas palavras arbitrárias de $R$. Tem-se que
							${\tt 0}^i{\tt 0}^{j+1}{\tt 1}^j={\tt 0}^{i+j+1}{\tt 1}^j=\not\in L$, pois se $i<j$ então $i+j+1\leq 2j$,
							e ${\tt 0}^j{\tt 0}^{j+1}{\tt 1}^j={\tt 0}^{2j+1}{\tt 1}^j\in L$. Portanto, $L$ não é regular.
        \item Sejam $L=\{w\in \{{\tt 0},{\tt 1}\}\}^*\,|\, n_{\tt 0}(w)=n_{\tt 1}(w)\}$ e $R=\{{\tt 0}\}^*$. Sejam as
				      palavras arbitrárias de $R$, ${\tt 0}^i$ e ${\tt 0}^j$, $i\not=j$. Segue-se que ${\tt 0}^i{\tt 1}^i\in L$ e
							${\tt 0}^j{\tt 1}^i\not\in L$. Portanto, $L$ não é regular.
        \item Seja $L=\{xx \,|\, x\in \{{\tt 0},{\tt 1}\}^*\}$. Seja $R=\{{\tt 0}\}^*$. Sejam
				      ${\tt 0}^i,{\tt 0}^j\in R$, $i\not=j$, duas palavras arbitrárias de $R$. Tem-se que
							${\tt 0}^i{\tt 1}{\tt 0}^i{\tt 1}\in L$ e  ${\tt 0}^j{\tt 1}{\tt 0}^i{\tt 1}\not\in L$.
							Logo, $L$ não é regular.
       \end{list}
 \item {\footnotesize Prove que os seguintes conjuntos não são linguagens regulares, utilizando o LB:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^m{\tt 1}^n\,|\, m<n\}$;
        \item $\{x{\tt 1}^n\,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|\leq n\}$;
        \item $\{{\tt 0}^n{\tt 1}^{2^n}\,|\, n\geq 0\}$;
        \item $\{x1y\,|\,x,y\in\{0,1\}^* \mbox{ e } |x|=|y|\}$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Seja $L=\{{\tt 0}^m{\tt 1}^n \,|\, m<n\}$. Suponha que $L$ seja regular. Sejam $k$ a constante do LB e
				      $z={\tt 0}^k{\tt 1}^{k+1}$. Sejam, de acordo com o LB, $u$, $v$ e $w$ tais que $z=uvw$, $v\not=\lambda$,
							$|uv|\leq k$ e $uv^iw\in L$ para todo $i\geq 0$. Mas, sendo $z=uvw$ e $|uv|\leq k$, $v$ só contém {\tt 0}s
							e, portanto, $uv^2w={\tt 0}^{k+|v|}{\tt 1}^{k+1}$. E sendo $v\not=\lambda$, $uv^2w\not\in L$.
              Isto contradiz o LB. Logo, $L$ não é regular.
        \item Seja $L=\{x{\tt 1}^n\,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|\leq n\}$. Suponha que $L$ seja regular.
				      Sejam $k$ a constante do LB e $z={\tt 0}^k{\tt 1}^k$. Sejam, de acordo com o LB, $u$, $v$ e $w$ tais que
							$z=uvw$, $v\not=\lambda$, $|uv|\leq k$ e $uv^iw\in L$ para todo $i\geq 0$. Mas, sendo $z=uvw$ e
							$|uv|\leq k$, $v$ só contém {\tt 0}s
							e, portanto, $uv^2w={\tt 0}^{k+|v|}{\tt 1}^k$. E sendo $v\not=\lambda$, $k+|v|>k$ e, assim, $uv^2w\not\in L$,
							o que contradiz o LB. Logo, $L$ não é regular.
        \item Seja $L=\{{\tt 0}^n{\tt 1}^{2^n} \,|\, n\geq 0\}$. Suponha que $L$ seja regular. Sejam $k$ a constante do LB
				      e $z={\tt 0}^k{\tt 1}^{2^k}$. Sejam, de acordo com o LB, $u$, $v$ e $w$ tais que $z=uvw$, $v\not=\lambda$,
              $|uv|\leq k$ e $uv^iw\in L$ p ara todo $i\geq 0$. Mas, sendo $z=uvw$ e $|uv|\leq k$, $v$ só contém {\tt 0}s
							e, portanto, $uv^2w={\tt 0}^{k+|v|}{\tt 1}^{2^k}$. E sendo $v\not=\lambda$, $uv^2w\not\in L$.
              Isto contradiz o LB. Logo, $L$ não é regular.
        \item Seja $L=\{x1y\,|\,x,y\in\{0,1\}^* \mbox{ e } |x|=|y|\}$. Seja a constante $k$ do LB, e seja $z=0^k10^k$. O
				      lema diz existem $u$, $v$ e $w$ tais $z=uvw$, $|u|>0$, $|uv|\leq k$ e $uv^iw\in L$ para todo $i\geq 0$. Como
							$z=0^k10^k$ e $|uv|\leq k$, $uv^2w=0^{k+|v|}10^k$; como $|v|>0$, segue-se que $uv^2w\not\in L$, contrariando
							o lema. Logo, $L$ não é regular.
       \end{list}
 \item {\footnotesize Prove que os seguintes conjuntos não são linguagens regulares, utilizando pro\-prie\-da\-des de fechamento:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^m{\tt 1}^n\,|\, m<n\}\cup\{{\tt 0}^m{\tt 1}^n\,|\, m>n\}$;
        \item $\{x{\tt 1}y\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(x)=n_{\tt 1}(y)\}$;
        \item $\{x{\tt 1}^n\,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|\leq n\}$;
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(w)=n_{\tt 1}(w)\}$;
        \item \mbox{$\{w\!\in\!\{{\tt 0},{\tt 1}\}^*| n_{\tt 0}(w)=n_{\tt 1}(w)\}\!-\!\{{\tt 0}^n{\tt 1}^n|n\geq 0\}$};
        \item $\{w\in\{{\tt 0},{\tt 1},{\tt 2}\}^*\,|\, n_{\tt 0}(w)\not=n_{\tt 1}(w)\}$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Seja $L=\{{\tt 0}^m{\tt 1}^n\,|\, m<n\}\cup\{{\tt 0}^m{\tt 1}^n\,|\,
              m>n\}$. Suponha que $L$ é regular. Então $\overline{L}\cap\{{\tt 0}\}^*
              \{{\tt 1}\}^*$ também é regular, pois as linguagens regulares são
              fechadas sob complementação e sob interseção. Mas, $\overline{L}
              \cap\{{\tt 0}\}^*\{{\tt 1}\}^*=\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$,
              que não é regular. Contradição! Logo, $L$ não é regular.
        \item Suponha que $L=\{x{\tt 1}y\in \{{\tt 0},{\tt 1}\}^*\,|\,n_0(x)=n_1(y)\}$ é regular. Como as linguagens
				      regulares são fechadas sob interseção e $\{{\tt 0}\}^*\{{\tt 1}\}^*$ é regular, então
							$L\cap\{{\tt 0}\}^*\{{\tt 1}\}^*$ deve ser regular. Mas $L\cap\{{\tt 0}\}^*\{{\tt 1}\}^*=
							\{{\tt 0}^n{\tt 1}^k\,|\, n<k\}$, que não é regular. Logo, $L$ não é regular.
        \item Seja $L=\{x{\tt 1}^n\,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|\leq n\}$. Suponha que $L$ é regular.
				      Então $L\cap\{{\tt 0}\}^*\{{\tt 1}\}^*$ também é regular, pois as linguagens regulares são fechadas
							sob interseção. Mas, $L\cap\{{\tt 0}\}^*\{{\tt 1}\}^*=\{{\tt 0}^m{\tt 1}^n\,|\,m\leq n\}$,
              que não é regular. Contradição! Logo, $L$ não é regular.
        \item Seja $L=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,n_{\tt 0}(w)=n_{\tt 1}(w)\}$. Então, como as linguagens regulares
              são fechadas sob interseção, $L\cap\{{\tt 0}\}^*\{{\tt 1}\}^*$ deve
              ser regular. Mas, $L\cap\{{\tt 0}\}^*\{{\tt 1}\}^*=\{{\tt 0}^n{\tt 1}^n
              \,|\,n\geq 0\}$, linguagem não regular. Contradição! Logo,
              $L$ não é regular.
        \item Seja $L=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(w)=n_{\tt 1}(w)\}-\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 0\}$. Se
              $L$ fosse regular, então $L\cap\{{\tt 1}\}^*\{{\tt 0}\}^*$ também seria, pois as
              linguagens regulares são fechadas sob interseção. Mas,
              $L\cap\{{\tt 1}\}^*\{{\tt 0}\}^*=\{{\tt 1}^n{\tt 0}^n\,|\,n\geq 1\}$, que não
              é regular. Portanto, $L$ não é regular.
        \item Seja $L=\{w\in\{{\tt 0},{\tt 1},{\tt 2}\}^*\,|\, n_{\tt 0}(w)\not=n_{\tt 1}(w)\}$. Se $L$ fosse regular,
				      $\overline{L}$ seria regular e $\overline{L}\cap\{{\tt 0}\}^*\{{\tt 1}\}^*$ também seria. Mas,
              $\overline{L}\cap\{{\tt 0}\}^*\{{\tt 1}\}^*=\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$, que não
              é regular. Portanto, $L$ não é regular.
       \end{list}

 \item {\footnotesize Sejam $L_1=\{{\tt 0}^n \,|\, n\geq 1000\}$ (regular), $L_2=\{{\tt 0}^n{\tt 1}^k \,|\, n\geq k\}$ (não regular) e
       $L_3=\{{\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}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_2-L_1$;
        \item $L_3-L_1$;
        \item $L_1\cap L_2$;
        \item $L_1\cap L_3$.
       \end{list}}

       \textit{Solução}:
        \begin{list}{\bf \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 $L_1\cap L_2=L_1$, que \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 Sejam $L_1=\{{0}^n \,|\, n \mbox{ é um número primo}\}$ e $L_2=\{{\tt 0}^k\}\{{\tt 0}\}^*$,
       em que $k$ é uma constante. Para cada linguagem a seguir, mostre que ela é regular ou que
			 não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1-L_2$;
        \item $L_1\cap L_2$;
        \item $L_1\cup L_2$.
       \end{list}}

       \textit{Solução}:
       Sabe-se que $L_1$ não é regular e $L_2$ é regular.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_3=\{{0}^n \,|\, n<k \mbox{ e }n \mbox{ é um número primo}\}$. Como este conjunto
							é \textit{finito}, é regular.
        \item Se $L_4=\{{0}^n \,|\, n\geq k \mbox{ e }n \mbox{ é um número primo}\}$ fosse regular,
              $L_4\cup L_3$ também seria, pois as linguagens regulares são fechadas sob união. Mas,
              $L_4\cup L_3=L_1$, que não é regular.
        \item Como $L_1\cup L_2=L_3\cup L_2$, $L_3$ e $L_2$ são regulares, segue-se por fechamento sob
              união que $L_1\cup L_2$ é regular.
       \end{list}
 \item {\footnotesize Seja $L$ uma linguagem regular sobre um alfabeto $\Sigma_1$. Prove que o conjunto de todas as 
       palavras sobre $\Sigma_2$ (que pode ser igual ou não a $\Sigma_1$) que têm como sufixo alguma
			 palavra de $L$ é linguagem regular.}

       \textit{Solução}:
        O conjunto das palavras sobre $\Sigma_2$ que têm como sufixo alguma palavra de $L$ é $\Sigma_2^*(L\cap\Sigma_2^*)$.
       Esta é regular, visto que $L$ e $\Sigma_2^*$ são regulares e as linguagens regulares são fechadas sob interseção e
			 concatenação.
 \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 um, dois ou três {\tt b}s$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ começa com {\tt a} e tem tamanho par$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ tem número par de {\tt a}s$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém {\tt bb}$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém exatamente um {\tt bb}$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ começa com {\tt a}, tem pelo menos um {\tt b} e termina com {\tt a}$\}$.
         \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $a^*ba^*(\lambda+ba^*(\lambda+ba^*))$.
        \item $a(a+b)((a+b)(a+b))^*$.
        \item $b^*(ab^*ab^*)^*$.
        \item $(a+b)^*bb(a+b)^*$.
        \item $(a+ba)^*bb(ab+a)^*$.
        \item $aa^*b(a+b)^*a$.
       \end{list}
 \item {\footnotesize Construa um AFD para cada uma das linguagens denotadas pelas ERs:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $(ab)^*ac$;
        \item $(ab)^*(ba)^*$;
        \item $(ab^*a)^*(ba^*b)^*$;
        \item $(aa+b)^*baab$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item AFD para  $(ab)^*ac$:

	        		\mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(90,12)\footnotesize
                \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

                \drawedge[curvedepth=3](0,1){\tt a}
                \drawedge[curvedepth=3](1,0){\tt b}
                \drawedge[curvedepth=0](1,2){\tt c}
               \end{picture}
              }

        \item AFD para $(ab)^*(ba)^*$:

	        		\mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(90,27)\footnotesize
                \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

                \drawedge[curvedepth=3](0,1){\tt a}
                \drawedge[curvedepth=0](0,2){\tt b}
                \drawedge[curvedepth=3](1,0){\tt b}
                \drawedge[curvedepth=3](2,3){\tt b}
                \drawedge[curvedepth=3](3,2){\tt a}
               \end{picture}
              }

        \item AFD para $(ab^*a)^*(ba^*b)^*$:

	        		\mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(90,27)\footnotesize
                \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

                \drawedge[curvedepth=3](0,1){\tt a}
                \drawedge[curvedepth=0](0,2){\tt b}
                \drawloop[loopangle=0](1){\tt b}
                \drawedge[curvedepth=3](1,0){\tt a}
                \drawloop[loopangle=180](2){\tt a}
                \drawedge[curvedepth=3](2,3){\tt b}
                \drawedge[curvedepth=3](3,2){\tt b}
               \end{picture}
              }
				
        \item AFD para $(aa+b)^*baab$:

	        		\mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(90,35)\footnotesize
                \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

                \node[Nmarks=ir, iangle=180](1)(20,20){}
                \node(2)(35,20){}
                \node(3)(50,20){}
                \node(4)(65,20){}
                \node[Nmarks=r](5)(80,20){}
                \node(6)(20,5){}

                \drawedge[curvedepth=0](1,2){\tt b}
                \drawedge[curvedepth=3](1,6){\tt a}
                \drawedge[curvedepth=3](6,1){\tt a}
                \drawloop[loopangle=270](2){\tt b}
                \drawedge[curvedepth=0](2,3){\tt a}
                \drawedge[curvedepth=0](3,4){\tt a}
                \drawedge[curvedepth=0](4,5){\tt b}
                \drawedge[curvedepth=6](4,6){\tt a}
                \drawedge[curvedepth=-12, ELside=r](5,2){\tt b}
                \drawedge[curvedepth=-6, ELside=r](5,3){\tt a}
               \end{picture}

              }
       \end{list}
 \item \label{eafder} {\footnotesize Construa ERs que denotem as linguagens reconhecidas pelos AFs mostrados na Figura~\ref{feafder}, utilizando o método
       descrito no livro.}
       \label{eafder}
       \begin{figure}
        \begin{center} \setlength{\unitlength}{1mm}
         \begin{picture}(40,37)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

          \node[Nmarks=i](0)(10,32){0}
          \node(1)(30,32){1}
          \node[Nmarks=r](2)(30,12){2}
          \node(3)(10,12){3}

          \drawedge[curvedepth=3](0,1){\tt a}
          \drawedge[curvedepth=0](0,3){\tt b}
          \drawedge[curvedepth=3](1,0){\tt a}
          \drawedge[curvedepth=3](1,2){\tt b}
          \drawedge[curvedepth=3](2,1){\tt b}
          \drawedge[curvedepth=0](2,3){\tt a}
          \drawloop[loopangle=225](3){{\tt a},{\tt b}}
					\put(20,5){\makebox(0,0)[ct]{\bf (a)}}
         \end{picture}
         \begin{picture}(40,37)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

          \node[Nmarks=i](0)(10,22){0}
          \node(1)(25,32){1}
          \node(2)(25,12){2}
          \node[Nmarks=r](3)(40,22){3}

          \drawedge[curvedepth=0](0,1){{\tt a},{\tt b}}
          \drawedge[curvedepth=0,ELside=r](0,2){\tt a}
          \drawedge[curvedepth=3](1,2){\tt a}
          \drawedge[curvedepth=0](1,3){\tt b}
          \drawedge[curvedepth=3](2,1){\tt b}
          \drawedge[curvedepth=0,ELside=r](2,3){\tt b}
					\put(25,5){\makebox(0,0)[ct]{\bf (b)}}
         \end{picture}
         \begin{picture}(40,37)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

          \node[Nmarks=i](0)(20,32){0}
          \node(1)(40,32){1}
          \node[Nmarks=ir](2)(30,12){2}

          \drawloop[loopangle=90](0){\tt a}
          \drawedge[curvedepth=0](0,1){\tt a}
          \drawloop[loopangle=0](1){\tt b}
          \drawedge[curvedepth=3](1,2){\tt c}
          \drawloop[loopangle=0](2){\tt c}
          \drawedge[curvedepth=3](2,1){\tt b}
          \drawedge[curvedepth=0](2,0){\tt a}
					\put(30,5){\makebox(0,0)[ct]{\bf (c)}}
         \end{picture}
        \end{center}

        \caption{\label{feafder} AFs do Exercício \ref{eafder}.}
       \end{figure}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Diagrama ER inicial:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(100,25)
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](i)(20,20){$i$}
         \node(0)(40,20){0}
         \node(1)(60,20){1}
         \node(2)(60,5){2}
         \node(f)(80,5){$f$}
         \node(3)(40,5){3}

         \drawedge[curvedepth=0](i,0){$\lambda$}
         \drawedge[curvedepth=3](0,1){$a$}
         \drawedge[curvedepth=0](0,3){$b$}
         \drawedge[curvedepth=3](1,0){$a$}
         \drawedge[curvedepth=3](1,2){$b$}
         \drawedge[curvedepth=3](2,1){$b$}
         \drawedge[curvedepth=0](2,3){$a$}
         \drawloop[loopangle=180](3){$a+b$}
         \drawedge[curvedepth=0](2,f){$\lambda$}
        \end{picture}
       }

       Eliminando-se o estado 3, já que $\#(3)=0$, obtém-se o diagrama ER:

	     \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,12)\footnotesize
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](i)(20,5){$i$}
         \node(0)(35,5){0}
         \node(1)(50,5){1}
         \node(2)(65,5){2}
         \node[Nmarks=r](f)(80,5){$f$}

         \drawedge[curvedepth=0](i,0){$\lambda$}
         \drawedge[curvedepth=3](0,1){$a$}
         \drawedge[curvedepth=3](1,0){$a$}
         \drawedge[curvedepth=3](1,2){$b$}
         \drawedge[curvedepth=3](2,1){$b$}
         \drawedge[curvedepth=0](2,f){$\lambda$}
        \end{picture}
       }


       Eliminando-se o estado 0 deste último, obtém-se o diagrama ER:
			
	     \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,17)\footnotesize
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](i)(20,5){$i$}
         \node(1)(35,5){1}
         \node(2)(50,5){2}
         \node[Nmarks=r](f)(65,5){$f$}

         \drawedge[curvedepth=0](i,1){$a$}
         \drawloop[loopangle=90](1){$aa$}
         \drawedge[curvedepth=3](1,2){$b$}
         \drawedge[curvedepth=3](2,1){$b$}
         \drawedge[curvedepth=0](2,f){$\lambda$}
        \end{picture}
       }

       Eliminando-se o estado 2:
			
	     \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,17)\footnotesize
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](i)(20,5){$i$}
         \node(1)(35,5){1}
         \node[Nmarks=r](f)(50,5){$f$}

         \drawedge[curvedepth=0](i,1){$a$}
         \drawloop[loopangle=90](1){$aa+bb$}
         \drawedge[curvedepth=0](1,f){$b$}
        \end{picture}
       }
	
       Eliminando-se o estado 1, obtém-se a ER: $a(aa+bb)^*b$.
			  \item Eliminando-se $2$ e depois $1$ obtém-se: $ab+(a+b+ab)(ab)^*(b+ab)$.
			  \item Acrescentando-se um estado $i$ com transições sob $\lambda$ para 0 e 2, e eliminando-se $1$ e $0$, nesta
				      ordem, obtém-se: $(\lambda+a^*ab^*c)(c+bb^*c+aa^*ab^*c)^*$.
       \end{list}
 \item {\footnotesize Obtenha GRs para as seguintes linguagens sobre \{{\tt 0},{\tt 1}\}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
       \item $\emptyset$;
       \item $\{\lambda\}$;
       \item o conjunto das palavras com tamanho múltiplo de 3;
       \item o conjunto das palavras com um número par de {\tt 0}s e um número par de {\tt 1}s;
       \item o conjunto das palavras em que cada {\tt 0} é seguido imediatamente de, no mínimo, dois {\tt 1}s;
       \item o conjunto das palavras em que cada {\tt 0} ocorre entre dois {\tt 1}s;
       \item o conjunto das palavras em que o antepenúltimo símbolo é {\tt 1};
       \item o conjunto das palavras que não contêm {\tt 0}s consecutivos nem {\tt 1}s consecutivos.
      \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $(\{P\},\{{\tt 0},{\tt 1}\},\{\},P)$.
        \item $(\{P\},\{{\tt 0},{\tt 1}\},\{P\,\rightarrow\,\lambda\},P)$.
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt 0}A \,|\, {\tt 1}A \,|\, \lambda$
               \item[\ ] $A\,\rightarrow\, {\tt 0}B \,|\, {\tt 1}B$
               \item[\ ] $B\,\rightarrow\, {\tt 0}P \,|\, {\tt 1}P$
             \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $pp\,\rightarrow\, {\tt 0}\, ip \,|\, {\tt 1}\, pi \,|\, \lambda$
               \item[\ ] $ip\,\rightarrow\, {\tt 0}\, pp \,|\, {\tt 1}\, ii$
               \item[\ ] $pi\,\rightarrow\, {\tt 0}\, ii \,|\, {\tt 1}\, pp$
               \item[\ ] $ii\,\rightarrow\, {\tt 0}\, pi \,|\, {\tt 1}\, ip$
             \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt 0}A \,|\, {\tt 1}P \,|\, \lambda$
               \item[\ ] $A\,\rightarrow\, {\tt 1}B$
               \item[\ ] $B\,\rightarrow\, {\tt 1}P$
             \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt 1}A \,|\, \lambda$
               \item[\ ] $A\,\rightarrow\, {\tt 1}A \,|\, {\tt 0}B \,|\, \lambda$
               \item[\ ] $B\,\rightarrow\, {\tt 1}A$
             \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt 0}P \,|\, {\tt 1}P \,|\, {\tt 1}A $
               \item[\ ] $A\,\rightarrow\, {\tt 0}B \,|\, {\tt 1}B$
               \item[\ ] $B\,\rightarrow\, {\tt 0} \,|\, {\tt 1}$
             \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt 0}A \,|\, {\tt 1}B \,|\, \lambda $
               \item[\ ] $A\,\rightarrow\, {\tt 1}B \,|\, \lambda$
               \item[\ ] $B\,\rightarrow\, {\tt 0}A \,|\, \lambda$
             \end{enumerate}
       \end{list}

 \item {\footnotesize Seja a GR $G=(\{P,A,B\},\{{\tt a},{\tt b}\},R,P)$, em que $R$ consta das regras:
       \begin{quote}
        $P \,\rightarrow\, {\tt a}P \,|\, {\tt b}P \,|\, {\tt a}A$ \\
        $A \,\rightarrow\, {\tt a} \,|\, {\tt b}B$ \\
        $B \,\rightarrow\, {\tt b}A$
       \end{quote}
       Construa, a partir de $G$, um AFN que aceite $L(G)$.}

       \textit{Solução}:
       AFN a partir de GR:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(60,35)
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](P)(20,20){P}
         \node(A)(40,20){A}
         \node(B)(60,20){B}
         \node[Nmarks=r](Z)(40,5){Z}

         \drawloop[loopangle=90](P){{\tt a},{\tt b}}
         \drawedge[curvedepth=0](P,A){\tt a}
         \drawedge[curvedepth=3](A,B){\tt b}
         \drawedge[curvedepth=0](A,Z){\tt a}
         \drawedge[curvedepth=3](B,A){\tt b}
        \end{picture}
       }
			\begin{comment}
 \item {\footnotesize Construa APDs para as seguintes linguagens:
         \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
          \item $\{{\tt 0}^n{\tt 1}^{2n}\,|\,n\geq 0\}$;
          \item $\{{\tt 0}^{3n}{\tt 1}^{2n}\,|\,n\geq 0\}$;
          \item $\{w{\tt 0}w^R\,|\,w\in\{{\tt 1},{\tt 2}\}^*\}$;
          \item $\{{\tt a}^n{\tt b}^k{\tt c}^n \,|\, n,k\geq 0\}$;
          \item $\{{\tt a}^n{\tt b}^i{\tt c}^j \,|\, n=i+j\}$.
          \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Um APD para $\{{\tt 0}^n{\tt 1}^{2n}\,|\,n\geq 0\}$:

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

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

                 \drawedge(0,1){${\tt 1},{\tt X}/\lambda$}

                 \drawloop[loopangle=90](0){${\tt 0},\lambda/{\tt XX}$}
                 \drawloop[loopangle=90](1){${\tt 1},{\tt X}/\lambda$}
                \end{picture}
               }
        \item Um APD para $\{{\tt 0}^{3n}{\tt 1}^{2n}\,|\,n\geq 0\}$:

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

                 \node[Nmarks=ir](0)(35,25){$0$}
                 \node[Nmarks=r](1)(70,25){$1$}
                 \node(0ll)(20,5){$0''$}
                 \node(0l)(50,5){$0'$}

                 \drawedge(0,1){${\tt 1},{\tt X}/\lambda$}
                 \drawedge[ELpos=55](0,0l){${\tt 0},\lambda/\lambda$}
                 \drawedge(0l,0ll){${\tt 0},\lambda/\lambda$}
                 \drawedge[ELpos=35](0ll,0){${\tt 0},\lambda/{\tt XX}$}

                 \drawloop[loopangle=90](1){${\tt 1},{\tt X}/\lambda$}
                \end{picture}
               }
        \item Um APD para $\{w{\tt 0}w^R\,|\,w\in\{{\tt 1},{\tt 2}\}^*\}$:

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

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

                 \drawedge(0,1){${\tt 0},\lambda/\lambda$}

                 \drawloop[loopangle=90](0){\shortstack{${\tt 1},\lambda/{\tt U}$ \\
                                                        ${\tt 2},\lambda/{\tt D}$}}
                 \drawloop[loopangle=90](1){\shortstack{${\tt 1},{\tt U}/\lambda$ \\
                                                        ${\tt 2},{\tt D}/\lambda$}}
                \end{picture}
               }
				\item Um APD para $\{{\tt a}^n{\tt b}^k{\tt c}^n \,|\, n,k\geq 0\}$:

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

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

                 \drawedge(0,1){${\tt b},\lambda/\lambda$}
                 \drawedge(1,2){${\tt c},{\tt X}/\lambda$}
                 \drawedge[ELside=r, curvedepth=-6](0,2){${\tt c},{\tt X}/\lambda$}

                 \drawloop[loopangle=90](0){${\tt a},\lambda/{\tt X}$}
                 \drawloop[loopangle=90](1){${\tt b},\lambda/\lambda$}
                 \drawloop[loopangle=90](2){${\tt c},{\tt X}/\lambda$}
                \end{picture}
               }
				 \item Um APD para $\{{\tt a}^n{\tt b}^i{\tt c}^i \,|\, n=i+j\}$:

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

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

                 \drawedge(0,1){${\tt b},{\tt X}/\lambda$}
                 \drawedge(1,2){${\tt c},{\tt X}/\lambda$}
                 \drawedge[ELside=r, curvedepth=-6](0,2){${\tt c},{\tt X}/\lambda$}

                 \drawloop[loopangle=90](0){${\tt a},\lambda/{\tt X}$}
                 \drawloop[loopangle=90](1){${\tt b},{\tt X}/\lambda$}
                 \drawloop[loopangle=90](2){${\tt c},{\tt X}/\lambda$}
                \end{picture}
               }
       \end{list}
			\end{comment}
 \item {\footnotesize Para as seguintes linguagens, construa APD, se possível. Se não for possível, construa APN.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{({\tt 01})^n{\tt 1}({\tt 10})^n\,|\,n\in\mathbb{N}\}$;
        \item $\{({\tt 01})^n{\tt 0}({\tt 10})^n\,|\,n\in\mathbb{N}\}$;
        \item $\{{\tt a}^n{\tt b}^{2n}{\tt c}^{2k}\,|\,n,k\in\mathbb{N}\}$;
        \item $\{{\tt a}^n{\tt b}^{2n}{\tt a}^{2k}\,|\,n,k\in\mathbb{N}\}$;
        \item $\{{\tt a}^n{\tt b}^{2n}{\tt a}^{2k}\,|\,n\geq 1,k\in\mathbb{N}\}$;
        \item $\{{\tt a}^n({\tt abc})^n\,|\,n\in\mathbb{N}\}$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item APD para $\{(\verb+01+)^n\verb+1+(\verb+10+)^n\,|\,n\in\mathbb{N}\}$:

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

               \node(1)(20,7){}
               \node[Nmarks=i, iangle=270](2)(40,7){}
               \node[Nmarks=r](3)(60,7){}
               \node(4)(80,7){}

               \drawedge[curvedepth=2](1,2){${\tt 1},\lambda/{\tt X}$}
               \drawedge[curvedepth=2](2,1){${\tt 0},\lambda/\lambda$}
               \drawedge[curvedepth=0](2,3){${\tt 1},\lambda/\lambda$}
               \drawedge[curvedepth=2](3,4){${\tt 1},\lambda/\lambda$}
               \drawedge[curvedepth=2](4,3){${\tt 0},{\tt X}/\lambda$}
              \end{picture}
              }

        \item APN para $\{(\verb+01+)^n\verb+0+(\verb+10+)^n\,|\,n\in\mathbb{N}\}$:

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

               \node(1)(20,7){}
               \node[Nmarks=i, iangle=270](2)(40,7){}
               \node[Nmarks=r](3)(60,7){}
               \node(4)(80,7){}

               \drawedge[curvedepth=2](1,2){${\tt 1},\lambda/{\tt X}$}
               \drawedge[curvedepth=2](2,1){${\tt 0},\lambda/\lambda$}
               \drawedge[curvedepth=0](2,3){${\tt 0},\lambda/\lambda$}
               \drawedge[curvedepth=2](3,4){${\tt 1},\lambda/\lambda$}
               \drawedge[curvedepth=2](4,3){${\tt 0},{\tt X}/\lambda$}
              \end{picture}
              }
        \item APD para $\{\verb+a+^n\verb+b+^{2n}{\tt c}^{2k}\,|\,n,k\in\mathbb{N}\}$:

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

               \node[Nmarks=ir, iangle=180](1)(20,10){}
               \node[Nmarks=r](2)(40,10){}
               \node(3)(60,10){}
               \node[Nmarks=r](4)(80,10){}

               \drawloop[loopangle=90](1){${\tt a},\lambda/{\tt XX}$}
							 \drawedge[curvedepth=0](1,2){${\tt b},{\tt X}/\lambda$}
							 \drawedge[curvedepth=-6,ELside=r](1,3){${\tt c},\lambda/\lambda$}
               \drawloop[loopangle=90](2){${\tt b},{\tt X}/\lambda$}
               \drawedge[curvedepth=0](2,3){${\tt c},\lambda/\lambda$}
               \drawedge[curvedepth=2](3,4){${\tt c},\lambda/\lambda$}
               \drawedge[curvedepth=2](4,3){${\tt c},\lambda/\lambda$}
              \end{picture}
              }
        \item APN para $\{\verb+a+^n\verb+b+^{2n}{\tt a}^{2k}\,|\,n,k\in\mathbb{N}\}$:

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

               \node[Nmarks=ir, iangle=180](1)(20,10){}
               \node[Nmarks=r](2)(40,10){}
               \node(3)(60,10){}
               \node[Nmarks=r](4)(80,10){}

               \drawloop[loopangle=90](1){${\tt a},\lambda/{\tt XX}$}
							 \drawedge[curvedepth=0](1,2){${\tt b},{\tt X}/\lambda$}
							 \drawedge[curvedepth=-6,ELside=r](1,3){${\tt a},\lambda/\lambda$}
               \drawloop[loopangle=90](2){${\tt b},{\tt X}/\lambda$}
               \drawedge[curvedepth=0](2,3){${\tt a},\lambda/\lambda$}
               \drawedge[curvedepth=2](3,4){${\tt a},\lambda/\lambda$}
               \drawedge[curvedepth=2](4,3){${\tt a},\lambda/\lambda$}
              \end{picture}
              }
        \item APD para $\{\verb+a+^n\verb+b+^{2n}{\tt a}^{2k}\,|\,n\geq 1,k\in\mathbb{N}\}$:

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

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

               \drawloop[loopangle=90](1){${\tt a},\lambda/{\tt XX}$}
							 \drawedge[curvedepth=0](1,2){${\tt b},{\tt X}/\lambda$}
               \drawloop[loopangle=90](2){${\tt b},{\tt X}/\lambda$}
               \drawedge[curvedepth=0](2,3){${\tt a},\lambda/\lambda$}
               \drawedge[curvedepth=2](3,4){${\tt a},\lambda/\lambda$}
               \drawedge[curvedepth=2](4,3){${\tt a},\lambda/\lambda$}
              \end{picture}
              }
        \item APD para $\{{\tt a}^n({\tt abc})^n\,|\,n\in\mathbb{N}\}$:

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

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

               \drawloop[loopangle=90](1){${\tt a},\lambda/{\tt A}$}
							 \drawedge[curvedepth=0](1,2){${\tt b},{\tt A}/\lambda$}
               \drawedge[curvedepth=0](2,3){${\tt c},{\tt A}/\lambda$}
               \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 APDs que reconheçam $\{{\tt a}^n{\tt b}^n\,|\, n\geq 0\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item por estado final;
        \item por pilha vazia.
       \end{list}}

       \textit{Solução}:

       Reconhecimento por estado final:

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

         \node[Nmarks=ir](0)(20,12.5){}
         \node(1)(45,12.5){}
         \node(2)(70,12.5){}
         \node[Nmarks=r](3)(95,12.5){}

         \drawedge(0,1){${\tt a},\lambda/{\tt F}$}
         \drawedge(1,2){${\tt b},{\tt X}/\lambda$}
         \drawedge(2,3){${\tt b},{\tt F}/\lambda$}
         \drawedge[curvedepth=-6, ELside=r](1,3){${\tt b},{\tt F}/\lambda$}

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

       Reconhecimento por pilha vazia:

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

         \node[Nmarks=i](1)(20,12.5){}
         \node(2)(45,12.5){}

         \drawedge(1,2){${\tt b},{\tt X}/\lambda$}

         \drawloop[loopangle=90](1){${\tt a},\lambda/{\tt X}$}
         \drawloop[loopangle=90](2){${\tt b},{\tt X}/\lambda$}
        \end{picture}
       }
 \item {\footnotesize Apresente uma GLC que gere $\{{\tt a}^n{\tt b}^n\,|\, n \mbox{ mod } 5\not=0\}$ que tenha uma
       única variável.}

       \textit{Solução}:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, {\tt a}^5 P {\tt a}^5\,|\, {\tt a}{\tt b} \,|\, {\tt a}^2{\tt b}^2
				                   \,|\, {\tt a}^3{\tt b}^3 \,|\, {\tt a}^4{\tt b}^4$
       \end{enumerate}

 \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_1L_2\cup L_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_1L_2\cup L_1^*$:
              \begin{enumerate}
               \item[\ ] $R\,\rightarrow\, PQ \,|\, S$
               \item[\ ] $S\,\rightarrow\, PS \,|\, \lambda$
              \end{enumerate}
							mais as regras dos dois ítens anteriores.
       \end{list}
 \item {\footnotesize Crie GLCs para:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt 0}^n{\tt 1}^k\,|\, 2n\leq k \leq 3n\}$;
        \item $L_2=\{{\tt a}^n{\tt b}^k{\tt c}^m\,|\,k=2n+m\}$;
        \item $(L_1\cup L_2)^2$;
        \item $(L_1\cup L_2)^*$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Para $L_1$:
              \begin{enumerate}
               \item[\ ] $X\,\rightarrow\, {\tt 0} X {\tt 11}\,|\, {\tt 0 }X {\tt 111}
                               \,|\, \lambda$
              \end{enumerate}
        \item Para $L_2$:
              \begin{enumerate}
               \item[\ ] $Y\,\rightarrow\, A B$
               \item[\ ] $A\,\rightarrow\, {\tt a} A {\tt bb}\,|\, \lambda$
               \item[\ ] $B\,\rightarrow\, {\tt b} B {\tt c} \,|\, \lambda$
              \end{enumerate}
        \item Para $(L_1\cup L_2)^2$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, Z Z$
               \item[\ ] $Z\,\rightarrow\, X \,|\, Y$
               \item[\ ] mais as regras de (a) e (b).
              \end{enumerate}
        \item Para $(L_1\cup L_2)^*$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, Z P \,|\, \lambda$
               \item[\ ] $Z\,\rightarrow\, X \,|\, Y$
               \item[\ ] mais as regras de (a) e (b).
              \end{enumerate}
       \end{list}
  \item {\footnotesize Seja $G$ a gramática:
	      \begin{enumerate}
	       \item[\ ] $P \,\rightarrow\, A B$
	       \item[\ ] $A \,\rightarrow\, {\tt a} A {\tt b} \,|\, {\tt c}$
	       \item[\ ] $B \,\rightarrow\, {\tt b} B {\tt c} \,|\, {\tt a}$
	      \end{enumerate}
	\begin{list}{\bf \alph{conta})}{\usecounter{conta}}
	 \item Desenvolva uma DME de {\tt acbbbacc}. 
	 \item Monte a árvore de derivação para a derivação construída em (a).
	 \item Defina $L(G)$ utilizando notação de conjunto.
	\end{list}}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $P\Rightarrow AB\Rightarrow{\tt a}A{\tt b}B\Rightarrow{\tt acb}B
               \Rightarrow{\tt acbb}B{\tt c}\Rightarrow{\tt acbbb}B{\tt cc}
               \Rightarrow{\tt acbbbacc}$
        \item AD:

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,70)\setlength{\unitlength}{1mm}
                \gasset{Nw=6, Nh=6, Nmr=3, AHnb=0}

                 \node(P)(50,65){$P$}
                 \node(A1)(27.5,50){$A$}
                 \node(B1)(72.5,50){$B$}
                 \node(a1)(12.5,35){\tt a}
                 \node(A2)(27.5,35){$A$}
                 \node(b1)(42.5,35){\tt b}
                 \node(b2)(57.5,35){\tt b}
                 \node(B2)(72.5,35){$B$}
                 \node(c1)(87.5,35){\tt c}
                 \node(c2)(27.5,20){\tt c}
                 \node(b3)(57.5,20){\tt b}
                 \node(B3)(72.5,20){$B$}
                 \node(c3)(87.5,20){\tt c}
                 \node(a2)(72.5,5){\tt a}

                 \drawedge(P,A1){}
                 \drawedge(P,B1){}
                 \drawedge(A1,a1){}
                 \drawedge(A1,A2){}
                 \drawedge(A1,b1){}
                 \drawedge(B1,b2){}
                 \drawedge(B1,B2){}
                 \drawedge(B1,c1){}
                 \drawedge(A2,c2){}
                 \drawedge(B2,b3){}
                 \drawedge(B2,B3){}
                 \drawedge(B2,c3){}
                 \drawedge(B3,a2){}
                \end{picture}
               }
        \item $L(G)=\{{\tt a}^n{\tt c}{\tt b}^n\,|\,n\geq 0\}
                    \{{\tt b}^n{\tt a}{\tt c}^n\,|\,n\geq 0\}$.
       \end{list}
 \item {\footnotesize Seja a gramática $G$ com as regras:
      \begin{enumerate}
       \item[\ ] $P\,\rightarrow\, AB\,|\,\lambda$
       \item[\ ] $A\,\rightarrow\, {\tt a}A{\tt b}\,|\,\lambda$
       \item[\ ] $B\,\rightarrow\, {\tt b}B{\tt a}\,|\,\lambda$
      \end{enumerate}
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item Que linguagem $G$ gera?
       \item Remova a ambiguidade de $G$ modificando-a o mínimo possível.
      \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(G)=\{{\tt a}^m{\tt b}^{m+n}{\tt a}^n\,|\, m,n\in\mathbb{N}\}$.
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, AB$
               \item[\ ] $A\,\rightarrow\, {\tt a}A{\tt b}\,|\,\lambda$
               \item[\ ] $B\,\rightarrow\, {\tt b}B{\tt a}\,|\,\lambda$
              \end{enumerate}
       \end{list}
 \item {\footnotesize Mostre que a GLC a seguir é ambígua:
      \begin{enumerate}
       \item[\ ] $E\,\rightarrow\, {\tt a}R\,|\,{\tt (}E{\tt )}R\,|\,{\tt a} \,|\,  {\tt (}E{\tt )}$
       \item[\ ] $R\,\rightarrow\, {\tt +}ER\,|\,{\tt *}ER\,|\,\lambda$
      \end{enumerate}}

       \textit{Solução}:
       Duas DMEs para {\tt a}:
			 \begin{itemize}
				\item $E\Rightarrow {\tt a}$
				\item $E\Rightarrow {\tt a}R\Rightarrow {\tt a}$
       \end{itemize}
 \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} \,|\, {\tt 1}$
       \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}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item FNC:
				      \begin{enumerate}
               \item[\ ]$S \,\rightarrow\, ZF \,|\, UG$
               \item[\ ]$A \,\rightarrow\, ZH \,|\, {\tt 1}$
               \item[\ ]$F \,\rightarrow\, SZ$
               \item[\ ]$G \,\rightarrow\, AU$
               \item[\ ]$H \,\rightarrow\, AZ$
               \item[\ ]$Z \,\rightarrow\, {\tt 0}$
               \item[\ ]$U \,\rightarrow\, {\tt 1}$
              \end{enumerate}
        \item FNG:
				      \begin{enumerate}
               \item[\ ]$S \,\rightarrow\, {\tt 0}SZ \,|\, {\tt 1}AU$
               \item[\ ]$A \,\rightarrow\, {\tt 0}AZ \,|\, {\tt 1}$
               \item[\ ]$Z \,\rightarrow\, {\tt 0}$
               \item[\ ]$U \,\rightarrow\, {\tt 1}$
              \end{enumerate}
       \end{list}
 \item {\footnotesize Construa uma gramática sem regras $\lambda$ equivalente à gramática a seguir e, em seguida,
       elimine símbolos inúteis:
	     \begin{enumerate}
        \item[\ ] $S\,\rightarrow\, A {\tt a} B \,|\, {\tt aa} B$
	      \item[\ ] $A\,\rightarrow\, \lambda$
        \item[\ ] $B\,\rightarrow\, {\tt bb} A \,|\, \lambda$
       \end{enumerate}}

       \textit{Solução}: \\
       Variáveis anuláveis: $\textit{VA}=\{A,B\}$. A GLC resultante é:
	     \begin{enumerate}
        \item[\ ] $S\,\rightarrow\,A{\tt a}B\,|\,A{\tt a}\,|\,{\tt a}B\,|\,{\tt a}\,|\,{\tt aa} B\,|\,{\tt aa}$
        \item[\ ] $B\,\rightarrow\, {\tt bb} A \,|\, {\tt bb}$
       \end{enumerate}
       Agora $A$ é inútil. Obtém-se:
	     \begin{enumerate}
        \item[\ ] $S\,\rightarrow\,{\tt a}B\,|\,{\tt a}\,|\,{\tt aa} B\,|\,{\tt aa}$
        \item[\ ] $B\,\rightarrow\, {\tt bb}$
       \end{enumerate}
 \item {\footnotesize Obtenha uma GLC na forma normal de Chomsky que gere $L(G)-\{\lambda\}$, se:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G$ tem as regras	\parbox[t]{12cm}{$P\,\rightarrow\, P(P) \,|\, \lambda$}
        \item $G$ tem as regras	\parbox[t]{12cm}{$P\,\rightarrow\, ABA$ \\
				            $A\,\rightarrow\, {\tt a}A \,|\, \lambda$ \\ $B\,\rightarrow\, {\tt b}B \,|\, \lambda$}
      	\end{list}}

       \textit{Solução}:
 			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Eliminando-se regras $\lambda$:
              \begin{enumerate}
				       \item[\ ] $P\,\rightarrow\, P(P) \,|\, (P) \,|\, P() \,|\, ()$
              \end{enumerate}
							FNC:
              \begin{enumerate}
				       \item[\ ] $P\,\rightarrow\, PX \,|\, AY \,|\, PZ \,|\, AB$
				       \item[\ ] $X\,\rightarrow\, AY$
				       \item[\ ] $Y\,\rightarrow\, PB$
				       \item[\ ] $Z\,\rightarrow\, AB$
				       \item[\ ] $A\,\rightarrow\, ($
				       \item[\ ] $B\,\rightarrow\, )$
              \end{enumerate}
        \item  Eliminando-se regras $\lambda$ e regras unitárias:
              \begin{enumerate}
				       \item[\ ] $P\,\rightarrow\, ABA \,|\, AA \,|\, AB \,|\, BA \,|\, {\tt a}A \,|\, {\tt a} \,|\,
							                     {\tt b}B \,|\, {\tt b}$
				       \item[\ ] $A\,\rightarrow\, {\tt a}A \,|\, {\tt a}$
				       \item[\ ] $B\,\rightarrow\, {\tt b}B \,|\, {\tt b}$
              \end{enumerate}
							FNC:
              \begin{enumerate}
				       \item[\ ] $P\,\rightarrow\, AZ \,|\, AA \,|\, AB \,|\, BA \,|\, XA \,|\, {\tt a} \,|\,
							                     YB \,|\, {\tt b}$
				       \item[\ ] $A\,\rightarrow\, XA \,|\, {\tt a}$
				       \item[\ ] $B\,\rightarrow\, YB \,|\, {\tt b}$
				       \item[\ ] $X\,\rightarrow\, {\tt a}$
				       \item[\ ] $Y\,\rightarrow\, {\tt b}$
				       \item[\ ] $Z\,\rightarrow\, BA$
              \end{enumerate}
      	\end{list}
 \item {\footnotesize Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ] $E\,\rightarrow\, E{\tt +}E \,|\, E{\tt *}E
                              \,|\, {\tt a}$
       \end{enumerate}
       Construa uma gramática na FNG equivalente a $G$.}

       \textit{Solução}:
       Eliminando-se a recursão direta à esquerda, obtém-se:
	\begin{enumerate}
	 \item[\ ] $E\,\rightarrow\,{\tt a}Z \,|\, {\tt a}$
	 \item[\ ] $Z\,\rightarrow\, {\tt +}EZ \,|\, {\tt *}EZ \,|\, {\tt +}E \,|\, {\tt *}E$
	\end{enumerate}
 \item {\footnotesize Obtenha uma GLC na FNG que gere $\{{\tt a}^m{\tt b}^n{\tt c}^k \,|\, n>m+k\}$. Em seguida, construa
       um AP que reconheça a mesma linguagem, a partir da GLC construída, de acordo com o método visto.}

       \textit{Solução}:
        Para $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\, n>m+k\}$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A B C$
               \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}
        Eliminando-se regras $\lambda$, obtém-se:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, ABC \,|\, AB \,|\, BC \,|\, B$
        \item[\ ] $A\,\rightarrow\, {\tt a} A {\tt b}\,|\, {\tt ab}$
        \item[\ ] $B\,\rightarrow\, {\tt b} B \,|\, {\tt b}$
        \item[\ ] $C\,\rightarrow\, {\tt b} C {\tt c}\,|\, {\tt bc}$
       \end{enumerate}
       Eliminando-se regras de cadeias, obtém-se:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, ABC \,|\, AB \,|\, BC \,|\, {\tt b} B \,|\, {\tt b}$
        \item[\ ] $A\,\rightarrow\, {\tt a} A {\tt b}\,|\, {\tt ab}$
        \item[\ ] $B\,\rightarrow\, {\tt b} B \,|\, {\tt b}$
        \item[\ ] $C\,\rightarrow\, {\tt b} C {\tt c}\,|\, {\tt bc}$
       \end{enumerate}
       Aplicando-se o Teorema 24 nas regras $P$:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, {\tt a}A{\tt b}BC \,|\, {\tt ab}BC \,|\,
                                    {\tt a}A{\tt b}B  \,|\, {\tt ab}B \,|\,
                                    {\tt b}BC \,|\, {\tt b}C \,|\,
                                    {\tt b} B \,|\, {\tt b}$
        \item[\ ] $A\,\rightarrow\, {\tt a} A {\tt b}\,|\, {\tt ab}$
        \item[\ ] $B\,\rightarrow\, {\tt b} B \,|\, {\tt b}$
        \item[\ ] $C\,\rightarrow\, {\tt b} C {\tt c}\,|\, {\tt bc}$
       \end{enumerate}
       Trocando-se terminais por variáveis:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow\, {\tt a}AYBC \,|\, {\tt a}YBC \,|\,
                                    {\tt a}AYB  \,|\, {\tt a}YB \,|\,
                                    {\tt b}BC \,|\, {\tt b}C \,|\,
                                    {\tt b} B \,|\, {\tt b}$
        \item[\ ] $A\,\rightarrow\, {\tt a} AY\,|\, {\tt a}Y$
        \item[\ ] $B\,\rightarrow\, {\tt b} B \,|\, {\tt b}$
        \item[\ ] $C\,\rightarrow\, {\tt b} CZ\,|\, {\tt b}Z$
        \item[\ ] $Y\,\rightarrow\, {\tt b}$
        \item[\ ] $Z\,\rightarrow\, {\tt c}$
       \end{enumerate}
       Um APN para a linguagem é $(\{i,f\},\Sigma,\{P,A,B,C,Y,Z\},\delta,\{i\},\{f\})$,
       em que $\delta$ consta das transições:
       \begin{itemize}
        \item $\delta(i,\lambda,\lambda)=\{[f,P]\}$;
        \item $\delta(f,{\tt a},P)=\{[f,AYBC],[f,YBC],[f,AYB],[f,YB]\}$;
        \item $\delta(f,{\tt b},P)=\{[f,BC],[f,C],[f,B],[f,\lambda]\}$;
        \item $\delta(f,{\tt a},A)=\{[f,AY],[f,Y]\}$;
        \item $\delta(f,{\tt b},B)=\{[f,B],[f,\lambda]\}$;
        \item $\delta(f,{\tt b},C)=\{[f,CZ],[f,Z]\}$;
        \item $\delta(f,{\tt b},Y)=\{[f,\lambda]\}$;
        \item $\delta(f,{\tt b},Z)=\{[f,\lambda]\}$.
       \end{itemize}

\end{enumerate}

\end{document}
