\documentclass[12pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\usepackage{latexsym}

\newcounter{conta}
\pagestyle{empty}
\begin{document}\footnotesize

 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2004 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova} \hfill 30/09/2004

\begin{enumerate}

 \item (3 pontos) Seja $L=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w$ n\~ao termina
       com {\tt 1} nem cont\'em {\tt 11}$\}$. Determine uma linguagem finita
       $F$ tal que $L=F^*$. Mostre que $L=F^*$.

       {\em Solu\c c\~ao\/}:

       $F=\{{\tt 0},{\tt 10}\}$. Ser\'a mostrado, por indu\c c\~ao sobre o tamanho
       de $w$, que $\forall w \,(w\in F^* \leftrightarrow w\in L)$. Considere
       $w=\lambda$: $\lambda \in F^*$ e $\lambda\in L$. Seja $n\geq 0$, e suponha,
       como hip\'otese de indu\c c\~ao, que $w\in F^* \leftrightarrow w\in L$ para
       $|w|\leq n$. Seja $z$ uma palavra de $n+1$ s\'{\i}mbolos. Ent\~ao:
       \begin{enumerate}
        \item[.] Suponha que $z\in F^*$. Pela defini\c c\~ao de fecho de Kleene,
              como $|z|>0$, $z=x{\tt 0}$ ou $z=x{\tt 10}$, onde $x\in F^*$. Pela
              hip\'otese de indu\c c\~ao, tanto em um caso como no outro, $x\in L$.
              Como $x\in L$ e $z=x{\tt 0}$ ou $z=x{\tt 10}$, n\~ao \'e poss\'{\i}vel
              $z$ terminar em {\tt 1} ou conter {\tt 11}, ou seja, $z\in L$.
        \item[.] Suponha que $z\in L$. Como $|z|>0$ e $z$ n\~ao termina com {\tt 1},
              $z=x{\tt 0}$. No caso em que $x$ n\~ao termina com {\tt 1}, $x\in L$
              (por defini\c c\~ao de $L$); e no caso em que $x$ termina com {\tt 1},
              $x=y{\tt 1}$ e $y$ n\~ao temina com {\tt 1}, ou seja, $z=y{\tt 10}$ e
              $y\in L$ (por defini\c c\~ao de $L$). Pela
              hip\'otese de indu\c c\~ao, num caso $x\in F^*$ e no outro $y\in F^*$.
              Como ${\tt 0}\in F$ e ${\tt 10}\in F$, segue-se que $z\in F^*$.
       \end{enumerate}

 \item (3 pontos) Construa gram\'aticas para as linguagens constitu\'{\i}das das
       palavras da forma ${\tt 0}^k{\tt 1}^n$, onde:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $k\leq n$.

              {\em Solu\c c\~ao\/}:

              $P \,\rightarrow\, {\tt 0}P{\tt 1} \,|\, P{\tt 1} \,|\, \lambda$

        \item $k\leq n\leq 3k$.

              {\em Solu\c c\~ao\/}:

              $P \,\rightarrow\, {\tt 0}P{\tt 1} \,|\, {\tt 0}P{\tt 11} \,|\,
               {\tt 0}P{\tt 111} \,|\, \lambda$

        \item $k+n$ \'e par.

              {\em Solu\c c\~ao\/}:

              $P \,\rightarrow\, {\tt 0}P{\tt 1} \,|\, {\tt 00}P \,|\, P{\tt 11}
                \,|\, \lambda$

       \end{list}

 \item (4 pontos) Para cada linguagem a seguir, apresente um diagrama de estados de um
       aut\^omato finito determin\'{\i}stico  que a reconhe\c ca. (N\~ao \'e
       preciso desenhar estados de erro.)
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01},{\tt 10}\}^*\{{\tt 00},{\tt 11}\}^*$.

              {\em Solu\c c\~ao\/}:

              \begin{center}
              \begin{picture}(200,140) \footnotesize
               \put(10,130){\vector(1,0){10}}
               \put(30,130){\oval(20,20)}
               \put(30,130){\oval(17,17)}
               \put(38,135){\vector(1,0){54}}
               \put(65,138){\makebox(0,0)[b]{{\tt 1}}}
               \put(92,125){\vector(-1,0){54}}
               \put(65,122){\makebox(0,0)[t]{{\tt 0}}}

               \put(35,122){\vector(0,-1){44}}
               \put(38,100){\makebox(0,0)[l]{{\tt 0}}}
               \put(25,78){\vector(0,1){44}}
               \put(22,100){\makebox(0,0)[r]{{\tt 1}}}
               \put(30,70){\oval(20,20)}
               \put(40,70){\vector(1,0){50}}
               \put(65,67){\makebox(0,0)[t]{{\tt 0}}}

               \put(100,130){\oval(20,20)}
               \put(100,120){\vector(0,-1){40}}
               \put(103,100){\makebox(0,0)[l]{{\tt 1}}}

               \put(100,70){\oval(20,20)}
               \put(100,70){\oval(17,17)}

               \put(108,75){\vector(1,0){54}}
               \put(135,78){\makebox(0,0)[b]{{\tt 0}}}
               \put(162,65){\vector(-1,0){54}}
               \put(135,62){\makebox(0,0)[t]{{\tt 0}}}
               \put(170,70){\oval(20,20)}

               \put(105,62){\vector(0,-1){44}}
               \put(108,40){\makebox(0,0)[l]{{\tt 1}}}
               \put(95,18){\vector(0,1){44}}
               \put(92,40){\makebox(0,0)[r]{{\tt 1}}}
               \put(100,10){\oval(20,20)}

              \end{picture}
              \end{center}

        \item $\{x{\tt 1}^n\,|\, x\in \{{\tt 0},{\tt 1}\}^* \mbox{ e }
               |x| \mbox{ e } n \mbox{ s\~ao \'{\i}mpares}\}$.

              {\em Solu\c c\~ao\/}:

              \begin{center}
              \begin{picture}(200,20) \footnotesize
               \put(10,10){\vector(1,0){10}}
               \put(30,10){\oval(20,20)}
               \put(38,15){\vector(1,0){54}}
               \put(65,18){\makebox(0,0)[b]{{\tt 0},{\tt 1}}}
               \put(92,5){\vector(-1,0){54}}
               \put(65,2){\makebox(0,0)[t]{{\tt 0}}}

               \put(100,10){\oval(20,20)}
               \put(108,15){\vector(1,0){54}}
               \put(135,18){\makebox(0,0)[b]{{\tt 1}}}
               \put(162,5){\vector(-1,0){54}}
               \put(135,2){\makebox(0,0)[t]{{\tt 0},{\tt 1}}}
               \put(170,10){\oval(20,20)}
               \put(170,10){\oval(17,17)}
 
              \end{picture}
              \end{center}

       \end{list}

 \item (2 pontos) Seja um aut\^omato finito n\~ao determin\'{\i}stico com
       transi\c c\~oes $\lambda$ $M=(E,\Sigma,\delta,I,F)$. O que seriam
       $E'$, $\delta'$, $I'$ e $F'$ em um aut\^omato finito n\~ao determin\'{\i}stico,
       sem transi\c c\~oes $\lambda$, $M'=(E',\Sigma,\delta',I',F')$
       equivalente a $M$?

       {\em Solu\c c\~ao\/}:

       \begin{enumerate}
        \item[.] $E'=E$;
        \item[.] $\delta'(e,a)=f\lambda(\delta(e,a))$ para todo $e\in E$, $a\in\Sigma$;
        \item[.] $I'=f\lambda(I)$;
        \item[.] $F'=F$.
       \end{enumerate}
       $f\lambda(X)$ \'e o conjunto de estados alcan\c c\'aveis a partir de estados de $X$
       utilizando-se apenas transi\c c\~oes $\lambda$.

 \item (3 pontos) Mostre que $\{{\tt b}{\tt a}^n{\tt b}^n\,|\,n\geq 0\}$ n\~ao \'e uma
       linguagem regular.

       {\em Solu\c c\~ao\/}:

       Suponha que $L$ \'e regular. Seja $z={\tt b}{\tt a}^k{\tt b}^k$, onde $k$ \'e a
       constante mencionada no lema do bombeamento. Sejam ainda $u$, $v$ e $w$ tais que
       $z=uvw$, $v\not=\lambda$ e $|uv|\leq k$. Pelo referido lema, deve-se ter
       $uv^iw\in L$ para todo $i\geq 0$. Tem-se dois casos:
       \begin{enumerate}
        \item[.] $u=\lambda$. Ent\~ao $v$ cont\'em o {\tt b} inicial, e $uv^0w={\tt a}^{k-|v|+1}{\tt b}^k$. Assim,
                 $uv^0w\not\in L$.
        \item[.] $u\not=\lambda$. Ent\~ao $u={\tt b}{\tt a}^{|u|-1}$, e, neste caso,
                 $uv^0w={\tt b}{\tt a}^{k-|v|}{\tt b}^k$. Como $|v|>0$,
                 $uv^0w\not\in L$.
       \end{enumerate}
       Isto contradiz o lema do bombeamento. Logo, $L$ n\~ao \'e regular.

 \item (1 ponto) Sabendo que $\{{\tt b}{\tt a}^n{\tt b}^n\,|\,n\geq 0\}$ n\~ao \'e uma
       linguagem regular, mostre que \[\{{\tt b}y\,|\,n_a(y)=n_b(y) \mbox{ e }
       |y|>100\}\] n\~ao \'e uma linguagem regular. ($n_s(w)$ \'e o n\'umero
       de ocorr\^encias do s\'{\i}mbolo $s$ na palavra $w$.)

       {\em Solu\c c\~ao\/}:

       Seja $L$ a linguagem em quest\~ao. Suponha que $L$ seja regular. Como
       $\{{\tt b}\}\{{\tt a}\}^*\{{\tt b}\}^*$ \'e regular, segue-se que
       \[L\cap \{{\tt b}\}\{{\tt a}\}^*\{{\tt b}\}^*=\{{\tt b}{\tt a}^n{\tt b}^n\,|\, n>50\}\]
       deve ser regular, j\'a que linguagens regulares s\~ao fechadas sob interse\c c\~ao.
       E como $\{{\tt b}{\tt a}^n{\tt b}^n\,|\, n\leq 50\}$ \'e regular, pois \'e finita,
       \[\{{\tt b}{\tt a}^n{\tt b}^n\,|\, n>50\}\cup\{{\tt b}{\tt a}^n{\tt b}^n\,|\, n\leq 50\}
         =\{{\tt b}{\tt a}^n{\tt b}^n\,|\, n\geq 0\}\]
       deve ser regular, j\'a que linguagens regulares s\~ao fechadas sob uni\~ao. Mas
       esta \'ultima n\~ao \'e regular.
       Contradi\c c\~ao. Logo, $L$ n\~ao \'e regular.

 \item (2 pontos) Mostre que se $R$ \'e linguagem regular e $L$  n\~ao \'e linguagem
       regular:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $R-L$ pode ser linguagem regular e pode n\~ao ser.

              {\em Solu\c c\~ao\/}:

       \begin{enumerate}
        \item[.] $\emptyset$ \'e regular, e $\emptyset-L=\emptyset$.
        \item[.] $\Sigma^*$ \'e regular, e $\Sigma^*-L=\overline{L}$, que n\~ao \'e
                 regular se $L$ n\~ao \'e.
       \end{enumerate}

        \item $L-R$ pode ser linguagem regular e pode n\~ao ser.

              {\em Solu\c c\~ao\/}:

       \begin{enumerate}
         \item[.] $\Sigma^*$ \'e regular, e $L-\Sigma^*=\emptyset$, sendo que $\emptyset$ \'e regular.
         \item[.] $\emptyset$ \'e regular, e $L-\emptyset=L$.
       \end{enumerate}

       \end{list}

\end{enumerate}

\end{document}
