\documentclass[11pt, a4paper]{report}

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

\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\vspace*{.5cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma W \hfill {18/05/2010}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 4 pontos.

\vspace*{2mm}
\noindent\framebox{\parbox{15.6cm}{\textbf{Aten\c{c}\~ao}:
Em todas as quest\~oes dever\~ao ser usados m\'etodos vistos em aula ou no livro-texto.
Qualquer resultado, mesmo que correto, obtido de forma \emph{ad-hoc\/} n\~ao ser\'a considerado.
Assim, \'e importante que explicite os passos executados em cada solu\c{c}\~ao apresentada.}}

\begin{enumerate}
 \item Construa diagramas de estado para AFNs que reconhe\c{c}am as linguagens a seguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto das palavras em $\{{\tt 0},{\tt 1}\}^*$, com quatro ou mais s\'{\i}mbolos, em que o
              antepenúltimo s\'{\i}mbolo (ou seja, o terceiro da direita para a esquerda) tenha ocorrência
              anterior. O AFN n\~ao pode ter mais de \underline{6 estados}.
        \item $(b+c)^*(b+a)^*+a^*c^*$. O AFN n\~ao pode ter mais de \underline{4 estados}.
       \end{list}

 \item Seja o AFN com o diagrama de estados:

       \begin{picture}(120,19)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(40,5){1}
        \node[Nmarks=i, iangle=0](2)(80,5){2}
        \node[Nmarks=r](3)(60,5){3}

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

       Obtenha um AFD equivalente ao AFN utilizando o m\'etodo visto (\textit{subset construction}).

 \item Encontre uma express\~ao regular que denote $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w
       \mbox{ não contém {\tt 000}}\}$ a partir de um AF que reconheça tal linguagem.
       
 \item Suponha que $n_s(w)$ seja o número de símbolos $s$ na palavra $w$, e sejam:
       \begin{itemize}
        \item $L_1=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,n_0(w) \mbox{ é par e } n_1(w) \mbox{ é ímpar}\}$
        \item $L_2=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ contém {\tt 000}}\}$
        \item $L_3=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ contém {\tt 111}}\}$
        \item $L_4=\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 0\}$
       \end{itemize}
       Para cada linguagem a seguir, diga se ela é ou não é regular. Justifique.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(L_1-L_2)\cup(L_1-L_3)$.
        \item $\overline{L_4}$.
        \item $\{{\tt 0}\}^*L_4\{{\tt 1}\}^*$.
       \end{list}
\end{enumerate}

\vspace*{.5mm}
\hrule

\vspace*{.5mm}
\hrule
\vspace*{2mm}
\noindent\framebox{\parbox{15.6cm}{
 AF: aut\^omato finito (de qualquer modalidade); \\
 AFN$\lambda$: aut\^omato finito n\~ao determin\'{\i}stico com transi\c{c}\~ao $\lambda$; \\
 AFN: aut\^omato finito n\~ao determin\'{\i}stico (sem transi\c{c}\~ao $\lambda$); \\
 AFD: aut\^omato finito determin\'{\i}stico.
}}
\end{document}
