\documentclass[11pt,a4paper]{report}

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

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

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\vspace*{20mm}
\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}/DINTER
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova} \hfill 08/10/2010

\vspace*{4mm}
Faça 5 das questões abaixo.

\begin{enumerate}

 \item Sejam $L_1=\{{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$ e $L_2=\{{\tt 0},{\tt 1}\}\{{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$.
       Faça AFDs que reconheçam e expressões regulares que denotem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1$;
        \item $L_2$;
        \item $\overline{L_2}$.
        \item $L_1\cap L_2$;
        \item $L_1-L_2$.
       \end{list}

 \item Seja a gram\'atica
       $(\{A,B\},\{{\tt 0},{\tt 1}\},R,A)$ em que $R$ consta de:
       \begin{enumerate}
        \item[\ ] $A \,\rightarrow\, {\tt 0} B$
        \item[\ ] $B \,\rightarrow\, A {\tt 1} \,|\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Apresente um esquema de deriva\c{c}\~ao que mostre como derivar qualquer palavra de $L(G)$.
        \item Descreva $L(G)$.
%        \item Prove que $L(G)$ \'e ou n\~ao \'e regular.
       \end{list}

% \item Obtenha um AFD que reconhe\c{c}a $(00+11)^*(01+10)^*$.

 \item Fa\c ca AFNs que reconhe\c{c}am o conjunto das palavras
       da forma $a_1a_2xb_1b_2$, sendo $a_1,a_2,b_1,b_2\in \{{\tt 0},{\tt 1}\}$ e $x\in \{{\tt 0},{\tt 1}\}^*$,
       para cada um dos casos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item  $a_1=a_2$ e $b_1=b_2$. (Máximo: 7 estados)
        \item  $a_1a_2=b_2b_1$. (Máximo: 10 estados)
        \item  $a_1a_2=b_1b_2$.  (Máximo: 10 estados)
       \end{list}
 \item Desenhe o diagrama de estados do AFN equivalente ao
       AFN$\lambda$ apresentado a seguir, obtido de acordo com o
       m\'etodo visto no curso.

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

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

         \drawloop[loopangle=90](1){{\tt a}}
         \drawedge(1,2){$\lambda$}
         \drawedge(1,3){\tt b}
         \drawloop[loopangle=270](2){{\tt c}}
         \drawedge(2,3){$\lambda$}
         \drawloop[loopangle=90](3){{\tt b}}
        \end{picture}
       } \\

\pagebreak
\vspace*{20mm}
 \item Obtenha, usando o método visto no curso, um AFD equivalente ao AFN abaixo:

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

         \node[Nmarks=i](1)(20,30){1}
         \node[Nmarks=i](2)(20,5){2}
         \node[Nmarks=r](3)(40,17.5){3}

         \drawloop[loopangle=90](1){\tt a}
         \drawedge[curvedepth=2](1,3){\tt a}
         \drawedge[curvedepth=2](3,1){\tt c}
         \drawloop[loopangle=270](2){\tt b}
         \drawedge[curvedepth=2](2,3){\tt b}
         \drawedge[curvedepth=2](3,2){\tt d}
        \end{picture}
       } \\

 \item Prove que $\{x\#y \,|\, x,y\in\{{\tt 0},{\tt 1}\}^+ \mbox{ e } \eta(x) \leq \eta(y)\}$ n\~ao \'e regular,
       sendo $\eta(w)$ o n\'umero representado por $w$ na base 2.

% \item Seja $L$ uma linguagem regular sobre o alfabeto $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$. Mostre que a linguagem  $\{w\in\Sigma^*\,|$ ou $w\in L$, ou $w$ cont\'em pelo menos um {\tt a} (mas n\~ao ambos)$\}$ \'e regular.

\end{enumerate}

\end{document}
