\documentclass[11pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}

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

\newcounter{conta}

\begin{document}

\vspace*{1cm}
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton José Vieira \\
\noindent{\em Primeira prova}/Solução do professor

\begin{enumerate}
 \item {\footnotesize Seja a linguagem $L=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, {\tt 00} \mbox{ é subpalavra de } w \mbox{ e }
        {\tt 11} \mbox{ não é subpalavra de } w\}$. Faça:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um AFD que reconheça $L$.
        \item Uma expressão regular que denote $L$.
       \end{list}}

       \textit{Solução:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item AFD:

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

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

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0, ELside=r](1,5){{\tt 1}}
               \drawedge[curvedepth=0](2,3){{\tt 0}}
               \drawedge[curvedepth=3](2,5){{\tt 1}}
               \drawedge[curvedepth=4](3,4){{\tt 1}}
               \drawloop[loopangle=90](3){{\tt 0}}
               \drawedge[curvedepth=4](4,3){{\tt 0}}
               \drawedge[curvedepth=3](5,2){{\tt 0}}
              \end{picture}
             }
        \item $(0+10)(10)^*0(0+10)^*(\lambda+1)$.
       \end{list}
 \item {\footnotesize Obtenha gramáticas para as seguintes linguagens sobre $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A linguagem da questão anterior.
        \item $\{{\tt 0}^n{\tt 1}^{n}{\tt 0}^n\,|\, n\geq 0\}$.
       \end{list}}

       \textit{Solução:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P \,\rightarrow\, {\tt 0}A \,|\, {\tt 10}A$ \\
              $A \,\rightarrow\, {\tt 0}B \,|\, {\tt 10}A$ \\
              $B \,\rightarrow\, {\tt 0}B \,|\, {\tt 10}B \,|\, \lambda \,|\, {\tt 1}$
        \item $X \,\rightarrow\, Y \,|\, \lambda$ \\
              $Y \,\rightarrow\, {\tt 0}YU{\tt 0} \,|\, {\tt 010}$ \\
              ${\tt 0}U \,\rightarrow\, U{\tt 0}$ \\
              ${\tt 1}U \,\rightarrow\, {\tt 11}$
       \end{list}
 \item {\footnotesize Seja a linguagem $X$ denotada por $0+11^*$. Construa autômatos finitos sem transições $\lambda$,
       que reconheçam $X$, com a seguinte característica:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O autômato tem um único estado inicial.
        \item O autômato tem um único estado final.
       \end{list}}

       \textit{Solução:}

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

               \put(0,25){\makebox(0,0)[l]{(a)}}
               \node[Nmarks=i](1)(25,20){}
               \node[Nmarks=r](2)(45,20){}
               \node[Nmarks=r](3)(25,5){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0, ELside=r](1,3){{\tt 1}}
               \drawloop[loopangle=0](3){{\tt 1}}

               \put(70,25){\makebox(0,0)[l]{(b)}}
               \node[Nmarks=i](1)(95,20){}
               \node[Nmarks=r](2)(115,20){}
               \node[Nmarks=i](3)(115,5){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0, ELside=r](3,2){{\tt 1}}
               \drawloop[loopangle=0](3){{\tt 1}}
              \end{picture}
             }
 \item {\footnotesize Seja o AFN$\lambda$ com o diagrama de estados:

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

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

         \drawedge[curvedepth=4](1,2){{\tt 0}}
         \drawedge[curvedepth=4](2,1){{\tt 1}}
         \drawedge[curvedepth=4](3,4){{\tt 1}}
         \drawedge[curvedepth=4](4,3){{\tt 0}}
         \drawedge[curvedepth=-12, ELside=r](1,3){$\lambda$}

         \drawloop[loopangle=90, ELside=l](1){{\tt 0}}
         \drawloop[loopangle=0, ELside=l](4){{\tt 1}}
        \end{picture}
       } \\
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Apresente o diagrama de estados de um AFN equivalente (use o método visto no curso).
        \item Apresente um AFD equivalente.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item AFN equivalente:
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,23)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

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

                \drawedge[curvedepth=4](1,2){{\tt 0}}
                \drawedge[curvedepth=4](2,1){{\tt 1}}
                \drawedge[curvedepth=4](3,4){{\tt 1}}
                \drawedge[curvedepth=4](4,3){{\tt 0}}
                \drawedge[curvedepth=-12, ELside=r](1,3){{\tt 0}}
                \drawedge[curvedepth=0](2,3){{\tt 1}}

                \drawloop[loopangle=90, ELside=l](1){{\tt 0}}
                \drawloop[loopangle=0, ELside=l](4){{\tt 1}}
               \end{picture}
              } \\
        \item AFD equivalente:
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,35)(-10,0)
                \gasset{Nw=8, Nh=6, Nmr=3, loopdiam=6}

                \node[Nmarks=ir](13)(20,25){13}
                \node[Nmarks=r](4)(40,25){4}
                \node(3)(60,25){3}
                \node[Nmarks=r](123)(20,5){123}
                \node[Nmarks=r](134)(40,5){134}

                \drawedge[curvedepth=0](13,4){{\tt 1}}
                \drawedge[curvedepth=0](13,123){{\tt 0}}
                \drawloop[loopangle=90, ELside=l](4){{\tt 1}}
                \drawedge[curvedepth=4](4,3){{\tt 0}}
                \drawedge[curvedepth=4](3,4){{\tt 1}}
                \drawloop[loopangle=180](123){{\tt 0}}
                \drawedge[curvedepth=4](123,134){{\tt 1}}
                \drawedge[curvedepth=4](134,123){{\tt 0}}
                \drawedge[curvedepth=0](134,4){{\tt 1}}
               \end{picture}
              }
       \end{list}
 \item {\footnotesize Seja $L$ uma linguagem regular sobre o alfabeto $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$. Mostre que
       a linguagem  $\{w\in\Sigma^*\,|\, \mbox{ ou } w\in L\mbox{ ou } w \mbox{ contém pelo menos um  {\tt a} (mas
       não ambos)}\}$ é regular.}

       \textit{Solução:}

       A linguagem em quest\~ao é $(L\cup\Sigma^*\{{\tt a}\}\Sigma^*)-(L\cap\Sigma^*\{{\tt a}\}\Sigma^*)$. Como a classe
			 das linguagens regulares é fechada sob as operações de união, interseção e diferença, segue-se ela é regular.
 \item {\footnotesize Prove que $\{xy\in\{a,b\}^*\,|\, |x|=|y|$ e $n_a(x)\geq n_b(y)\}$ não é regular. ($n_s(w)$ é o número
       de símbolos $s$ na palavra $w$.)}

       \textit{Solução:}

       Seja $L$ a linguagem em questão, e suponha que ela seja regular. Então o lema do bombeamento se aplica.
			 Seja $k$ a constante lá referida e $z={\tt b}^k{\tt a}^k$. Como $z\in L$ e $|z|>k$, sejam $u$ $v$ e $w$ tais
			 que $z=uvw$, $|uv|\leq k$ e $|v|>0$. Como $uvw={\tt b}^k{\tt a}^k$ e $|uv|\leq k$, $v$ só contém {\tt b}s e,
			 portanto, $uv^2w={\tt b}^{k+|v|}{\tt a}^k$. Como $|v|>0$, tem-se dois casos:
       \begin{enumerate}
        \item[1.] $|v|$ ímpar. Então $|uv^2w|$ é ímpar e, portanto, $uv^2w\not\in L$.
        \item[2.] $|v|>0$ par. Então a primeira metade de $uv^2w$ não contém {\tt a}s, mas a segunda contém
                  {\tt b}s (pelo menos um no seu início). Segue-se que $uv^2w\not\in L$.
       \end{enumerate}
       Assim, $uv^2w\not\in L$, contradizendo o lema do bombeamento. Logo, a linguagem não é regular.

\end{enumerate}

\end{document}
 
