\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}
\newcounter{conta2}

\begin{document}\footnotesize
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2004 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova/Solu\c c\~ao do professor} \hfill 22/04/2004

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

 \item Seja $L=\{\lambda,{\tt a},{\tt b}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e $L^0$?

              {\em Solu\c c\~ao:} $L^0=\{\lambda\}$.

        \item Que linguagem \'e $L^2$?

              {\em Solu\c c\~ao:} $L^2=\{\lambda,{\tt a},{\tt b},{\tt aa},{\tt ab},
                   {\tt ba},{\tt bb}\}$.

        \item Que linguagem \'e $L^n$, para $n\geq 0$?

              {\em Solu\c c\~ao:} $L^n=\{w\in\{{\tt a},{\tt b}\}^*\,|\,0\leq |w|\leq n\}$.

        \item Quantas palavras tem $L^n$, para $n\geq 0$?

              {\em Solu\c c\~ao:} $|L^n|=\sum_{k=0}^n 2^k=2^{n+1}-1$.
       \end{list}

 \item Descreva mais formalmente (usando conjuntos finitos, concatena\c c\~ao,
       uni\~ao, interse\c c\~ao, fecho de Kleene, etc.) as seguintes linguagens
       sobre o alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item O conjunto das palavras com um n\'umero \'{\i}mpar de s\'{\i}mbolos.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ come\c ca e termina com o
                mesmo s\'{\i}mbolo$\}$.

              {\em Solu\c c\~ao:} $\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*\{{\tt 0}\}\cup
                \{{\tt 1}\}\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\cup\{{\tt 0},{\tt 1}\}$.

        \item O conjunto $X$ definido recursivamente assim:
              \begin{list}{\arabic{conta2})}{\usecounter{conta2}}
               \item $\lambda\in X$;
               \item se $x\in X$, ent\~ao ${\tt 1}x\in X$ e $x{\tt 0}\in X$.
              \end{list}

              {\em Solu\c c\~ao:} $\{{\tt 1}\}^*\{{\tt 0}\}^*$.

        \item O conjunto das palavras com um n\'umero par de {\tt 0}'s e \'{\i}mpar de {\tt 1}'s.
              (Sugest\~ao: use o operador de interse\c c\~ao.)

              {\em Solu\c c\~ao:} $(\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\})^*\{{\tt 1}\}^*\cap
                  (\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*)
                       (\{{\tt 1}\}\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*)^*$.
       \end{list}

 \item Sobre gram\'aticas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada pela gram\'atica $G$ definida a seguir?

              $G=(\{P,Z\},\{{\tt 0},{\tt 1}\},R,P)$.
               \begin{enumerate}
                \item[$R$:] $P\,\rightarrow\,{\tt 0} P {\tt 1}\,|\, Z$
                \item[\ ]   $Z\,\rightarrow\,{\tt 0} Z \,|\, {\tt 0}$
               \end{enumerate}

              {\em Solu\c c\~ao:} $L(G)=\{{\tt 0}^n{\tt 1}^k\,|\, n>k\geq 0\}$.

        \item Obtenha uma gram\'atica que gere $\{wxw^R\,|\,w\in\{{\tt a},{\tt b}\}^*, x\in\{{\tt b}\}^*$
               e $|x|$ \'e \'{\i}mpar$\}$.

              {\em Solu\c c\~ao:} $P\,\rightarrow\,{\tt a} P {\tt a}\,|\,{\tt b} P {\tt b}\,|\,{\tt b}$
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}^*\{{\tt 1}\}^+\{{\tt 01}\}^*$.

              {\em Solu\c c\~ao:} 
\begin{center}
\begin{picture}(331,45) \footnotesize
\put(10,30){\vector(1,0){10}}
\put(30,30){\oval(20,20)}
\put(30,30){\makebox(0,0){$1$}}
\put(25,22){\line(0,-1){10}}
\put(30,12){\oval(10,10)[b]}
\put(35,12){\vector(0,1){10}}
\put(30,4){\makebox(0,0)[t]{{\tt 0}}}
\put(40,30){\vector(1,0){30}}
\put(55,33){\makebox(0,0)[b]{{\tt 1}}}

\put(80,30){\oval(20,20)}
\put(80,30){\oval(17,17)}
\put(80,30){\makebox(0,0){$2$}}
\put(75,22){\line(0,-1){10}}
\put(80,12){\oval(10,10)[b]}
\put(85,12){\vector(0,1){10}}
\put(80,4){\makebox(0,0)[t]{{\tt 1}}}
\put(90,30){\vector(1,0){30}}
\put(105,33){\makebox(0,0)[b]{{\tt 0}}}

\put(130,30){\oval(20,20)}
\put(130,30){\makebox(0,0){$3$}}
\put(138,35){\vector(1,0){34}}
\put(155,38){\makebox(0,0)[b]{{\tt 1}}}
\put(172,25){\vector(-1,0){34}}
\put(155,22){\makebox(0,0)[t]{{\tt 0}}}

\put(180,30){\oval(20,20)}
\put(180,30){\oval(17,17)}
\put(180,30){\makebox(0,0){$4$}}
\end{picture}
\end{center}

        \item $\{{\tt a}^k{\tt b}^n\,|\, k+n\not= 2\}$.

              {\em Solu\c c\~ao:} 
\begin{center}
\begin{picture}(331,95) \footnotesize
\put(10,80){\vector(1,0){10}}
\put(30,80){\oval(20,20)}
\put(30,80){\oval(17,17)}
\put(30,80){\makebox(0,0){$1$}}
\put(40,80){\vector(1,0){30}}
\put(55,83){\makebox(0,0)[b]{{\tt a}}}

\put(80,80){\oval(20,20)}
\put(80,80){\oval(17,17)}
\put(80,80){\makebox(0,0){$2$}}
\put(90,80){\vector(1,0){30}}
\put(105,83){\makebox(0,0)[b]{{\tt a}}}

\put(130,80){\oval(20,20)}
\put(130,80){\makebox(0,0){$3$}}
\put(140,80){\vector(1,0){30}}
\put(155,83){\makebox(0,0)[b]{{\tt a}}}

\put(180,80){\oval(20,20)}
\put(180,80){\oval(17,17)}
\put(180,80){\makebox(0,0){$4$}}
\put(188,75){\line(1,0){10}}
\put(198,80){\oval(10,10)[r]}
\put(198,85){\vector(-1,0){10}}
\put(206,80){\makebox(0,0)[l]{{\tt a}}}
\put(172,72){\vector(-1,-1){35}}
\put(157,52){\makebox(0,0)[l]{{\tt b}}}

\put(130,30){\oval(20,20)}
\put(130,30){\oval(17,17)}
\put(130,30){\makebox(0,0){$5$}}
\put(125,22){\line(0,-1){10}}
\put(130,12){\oval(10,10)[b]}
\put(135,12){\vector(0,1){10}}
\put(130,4){\makebox(0,0)[t]{{\tt b}}}

\put(130,70){\vector(0,-1){30}}
\put(133,55){\makebox(0,0)[l]{{\tt b}}}

\put(80,70){\vector(0,-1){30}}
\put(83,55){\makebox(0,0)[l]{{\tt b}}}
\put(80,30){\oval(20,20)}
\put(80,30){\makebox(0,0){$6$}}
\put(90,30){\vector(1,0){30}}
\put(105,33){\makebox(0,0)[b]{{\tt b}}}

\put(30,70){\vector(0,-1){30}}
\put(33,55){\makebox(0,0)[l]{{\tt b}}}
\put(30,30){\oval(20,20)}
\put(30,30){\oval(17,17)}
\put(30,30){\makebox(0,0){$7$}}
\put(40,30){\vector(1,0){30}}
\put(55,33){\makebox(0,0)[b]{{\tt b}}}

\end{picture}
\end{center}

        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ com n\'umero \'{\i}mpar
              de {\tt 0}'s e sem {\tt 0}'s consecutivos.

              {\em Solu\c c\~ao:} 
\begin{center}
\begin{picture}(331,100) \footnotesize
\put(10,70){\vector(1,0){10}}
\put(30,70){\oval(20,20)}
\put(30,70){\makebox(0,0){$p1$}}
\put(35,78){\line(0,1){10}}
\put(30,88){\oval(10,10)[t]}
\put(25,88){\vector(0,-1){10}}
\put(30,96){\makebox(0,0)[b]{{\tt 1}}}
\put(40,70){\vector(1,0){30}}
\put(55,73){\makebox(0,0)[b]{{\tt 0}}}

\put(80,70){\oval(20,20)}
\put(80,70){\oval(17,17)}
\put(80,70){\makebox(0,0){$i0$}}
\put(80,60){\vector(0,-1){30}}
\put(83,45){\makebox(0,0)[l]{{\tt 1}}}

\put(80,20){\oval(20,20)}
\put(80,20){\oval(17,17)}
\put(80,20){\makebox(0,0){$i1$}}
\put(88,25){\line(1,0){10}}
\put(98,20){\oval(10,10)[r]}
\put(98,15){\vector(-1,0){10}}
\put(106,20){\makebox(0,0)[l]{{\tt 1}}}
\put(70,20){\vector(-1,0){30}}
\put(55,23){\makebox(0,0)[b]{{\tt 0}}}

\put(30,20){\oval(20,20)}
\put(30,20){\makebox(0,0){$p0$}}
\put(30,30){\vector(0,1){30}}
\put(33,45){\makebox(0,0)[l]{{\tt 1}}}

\end{picture}
\end{center}

       \end{list}

 \item Sejam dois AFD's $M_1=(E_1,\Sigma,\delta_1,i_1,F_1)$ e$M_2=(E_2,\Sigma,\delta_2,i_2,F_2)$.
       Fazendo-se o ``produto'' de $M_1$ e $M_2$ para obter o AFD
       $M_3=(E_1\times E_2,\Sigma,\delta_3,[i_1,i_2],F_3)$ tal que $L(M_3)=L(M_1)\cup L(M_2)$,
       como seriam obtidos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\delta_3$?

              {\em Solu\c c\~ao:} Para cada $[e_1,e_2]\in E_1\times E_2$ e $a\in\Sigma$:
                   $\delta_3([e_1,e_2],a)=[\delta_1(e_1,a),\delta_2(e_2,a)]$.
        \item $F_3$?

              {\em Solu\c c\~ao:} $F_3=F_1\times E_2\cup E_1\times F_2$.
       \end{list}

\end{enumerate}

\end{document}

