\documentclass[11pt,a4paper]{report}

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

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

\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
 
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2015 \\
Professor: Newton José Vieira \\
 {\bf Primeira Prova} \hfill 15/9/2015

\vspace*{3mm}
\noindent Cada questão vale 4 pontos.

\vspace*{3mm}
\begin{enumerate}
 \item Expresse as linguagens a seguir utilizando operações sobre \emph{conjuntos finitos} de palavras. Só podem ser
       usadas as operações: concatenação, união e fecho de Kleene.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,w\mbox{ contém no máximo dois }{\tt b}\mbox{s}\}$.
			  \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,\mbox{ a subpalavra }{\tt ab}\mbox{ ocorre um número par de vezes em }w\}$.
       \end{list}

 \item Construa gramáticas para as linguagens da questão 1.

 \item Explique porque os problemas a seguir são decidíveis:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item Dado um AFN, determinar se ele reconhece uma linguagem finita.
			  \item Dados 3 AFDs $M_1$, $M_2$ e $M_3$, determinar se $L(M_1)-L(M_2)=L(M_3)$.
       \end{list}

 \item Construa AFDs que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,\mbox{ a subpalavra }{\tt ab}\mbox{ ocorre um número par de vezes em }w\}$.
				\item $\{{\tt 000},{\tt 1}\}^*\{{\tt 0},{\tt 11}\}^*$.
       \end{list}

 \item Para cada linguagem a seguir, mostre que ela é regular ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $\{x{\tt a}x\,|\,x\in\{{\tt b},{\tt c}\}^*\}$.
			  \item $\{x\,|\,ax\in L\}$, caso $L$ seja uma linguagem regular. Aqui $a$ é um símbolo do
				      alfabeto de $L$.
       \end{list}

 \item Obtenha um AFN equivalente a:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,15)
          \gasset{Nw=6, Nh=6, Nmr=6, loopdiam=6}

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

          \drawloop[loopangle=90](1){\tt a}
          \drawedge[curvedepth=3](1,2){\tt b}
          \drawloop[loopangle=90](2){\tt b}
          \drawedge[curvedepth=3](2,3){\tt c}
          \drawloop[loopangle=90](3){\tt c}
          \drawedge[curvedepth=3](3,2){$\lambda$}
          \drawedge[curvedepth=3](2,1){$\lambda$}
         \end{picture}
        }
      \end{center}
     usando o método de obtenção de AFN a partir de AFN$\lambda$ visto em aula (ou no livro-texto).
		 Explicite o cálculo de $\delta'(e,s)$ para cada par $(e,s)\in\{1,2,3\}\times\{{\tt a},{\tt b},
		 {\tt c}\}$ tal que $|\delta'(e,s)|>1$.
\end{enumerate}

\end{document}

