\documentclass[11pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
%\usepackage[brazil]{babel}    % [brazil] or [english]
\usepackage[latin1]{inputenc}
%\usepackage[T1]{fontenc} 

\newcounter{conta}

\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
{\it Fundamentos da Teoria da Computa\c{c}\~{a}o}
 \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2007 \\
Professor: Newton Jos\'{e} Vieira \\
Monitora: Isabel Gomes Barbosa \\
 
\noindent {\bf Lista de Exerc\'{\i}cios} \hfill Valor: 2 pts

\vspace*{3mm}
\noindent {\bf Aten\c{c}\~ao:} O primeiro exerc\'{\i}cio vale 1 ponto e os
outros dois 0,5 ponto cada um. As folhas de respostas devem ser montadas a
partir das telas obtidas usando o JFLAP e entregues \`a monitora, no
hor\'ario de monitoria, at\'e o dia 25/04/2007 (quarta-feira) \`as 11h.
\vspace*{3mm}

\begin{enumerate}
 \item Utilizando o programa JFLAP, construa AFN's $N_{1}$ e $N_{2}$ que reconheçam as linguagens $L_{1} = \{ba^{n}b|n \geq 0\}$ e
$L_{2} = \{b^{2n}a|n \geq 0\}$, respectivamente.

A partir dos AFN's $N_{1}$ e $N_{2}$ obtidos, gere no próprio programa JFLAP AFD's mínimos para as seguintes linguagens:

\begin{enumerate}
	\item[a.] $L_{1} \cup L_{2}$;
	\item[b.] $L_{1}L_{2}$;
		\item[c.] ${L_{1}}^{*}$.
\end{enumerate}

\item Construa no programa JFLAP o diagrama de estados de um AFD mínimo para a linguagem $L=\{w \in {\{a,b,c\}}^*|w \mbox{ não contém a substring cba}\}$. A partir do AFD construído, obtenha uma expressão regular e uma gramática regular para a linguagem.

\small{ \textit{Dica: Obtenha inicialmente um AFN para o complemento da linguagem (conjunto de palavras que contém a substring $cba$), converta o AFN para um AFD, troque os estados de aceitação e de não aceitação do AFD e, por fim, minimize o AFD. Utilize as funções presentes no programa JFLAP para facilitar o seu trabalho!}}
 
\item Utilize o programa JFLAP para obter um AFD mínimo para a linguagem 

\ \ \ $L=\{w \in {\{a,b\}}^*|n_{a}(w)\mbox{ é par} \mbox{ e } n_{b}(w) \mbox { é divisível por 3}\}$.

Em seguida, modifique o AFD obtido para que o mesmo passe a reconhecer as linguagens abaixo:

\begin{enumerate}
	\item[a.] $L=\{w \in {\{a,b\}}^*|n_{a}(w)\mbox{ é ímpar} \mbox{ e } n_{b}(w) \mbox{ mod }3=1\}$;
	\item[b.] $L=\{w \in {\{a,b\}}^*|n_{a}(w)\mbox{ é ímpar} \mbox{ ou } n_{b}(w) \mbox{ mod }3 \neq 0\}$.
\end{enumerate}

\end{enumerate}

\end{document}
