\documentclass[12pt,a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

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

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

\vspace*{3mm}
\begin{enumerate}
 \item (3 pontos) Seja $L=\{\lambda,{\tt 0},{\tt 1}\}$.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
				\item Que linguagem é $L^n$ para $n\geq 0$?
%				\item Quantas palavras de $n$ símbolos há em $L^*$?
				\item Quantas palavras tem $L^n$ para $n\geq 0$?
       \end{list}
 \item (4 pontos) Expresse as linguagens a seguir utilizando operações sobre \emph{conjuntos finitos} de palavras de
       $\{{\tt 0},{\tt 1}\}^*$. Use apenas os operadores de \emph{união}, \emph{concatenação} e \emph{fecho
			 de Kleene}. Considere o alfabeto como sendo $\{{\tt 0},{\tt 1}\}$.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item o conjunto das palavras que contêm pelo menos um {\tt 0} \textbf{e} um {\tt 1};
%       \item o conjunto das palavras em que todo {\tt 0} (quando houver) é imediatamente seguido de dois
%				      {\tt 1}s consecutivos (no mínimo); exemplos: $\lambda$, {\tt 1}, {\tt 101111}, {\tt 10111011};
        \item o conjunto das palavras  de $\{{\tt 0}\}^*\{{\tt 1}\}^*$ de tamanho par.
       \end{list}
 \item (4 pontos) Seja a gramática $G=(\{P,A,B\},\{{\tt a},{\tt b}\},R,P)$ em que $R$ tem as regras:
       \begin{enumerate}
        \item[\ \ \ ] $P\rightarrow AB$
        \item[\ \ \ ] $A\rightarrow {\tt a} A \,|\, \lambda$
        \item[\ \ \ ] $B\rightarrow {\tt a} B {\tt b} \,|\, \lambda$
       \end{enumerate}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item Que linguagem é $L(G)$?
			  \item Apresente um esquema de derivação que mostre como gerar qualquer palavra de $L(G)$.
%			  \item No esquema apresentado, quantos passos são gastos para gerar uma palavra de $n$ símbolos?
       \end{list}
 \item (3 pontos) Minimize o AFD com o seguinte diagrama de estados:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(100,40)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(10,30){1}
          \node[Nmarks=r](2)(10,10){2}
          \node(3)(30,30){3}
          \node(4)(50,30){4}
          \node(5)(30,10){5}
          \node[Nmarks=r](6)(50,10){6}

          \drawedge[curvedepth=0](1,2){\tt 0}
          \drawedge[curvedepth=0](1,3){\tt 1}
          \drawloop[loopangle=270](2){\tt 0}
          \drawedge[curvedepth=0](2,3){\tt 1}
          \drawedge[curvedepth=0](3,5){\tt 0}
          \drawedge[curvedepth=2](3,4){\tt 1}
          \drawedge[curvedepth=2](4,3){\tt 1}
          \drawedge[curvedepth=-8,ELside=r](4,1){\tt 0}
          \drawedge[curvedepth=0](5,6){\tt 0}
          \drawedge[curvedepth=0](5,4){\tt 1}
          \drawedge[curvedepth=0](6,4){\tt 1}
          \drawedge[curvedepth=6](6,2){\tt 0}
         \end{picture}
        }
       \end{center}
 \item (4 pontos: 1,1,2) Encontre AFDs que reconheçam as linguagens:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\{{\tt 01},{\tt 1}\}^*$.
        \item O complemento da linguagem anterior.
%        \item $\{{\tt 01},{\tt 1}\}^*\cap(\{{\tt 0},{\tt 1}\},\{{\tt 0},{\tt 1}\})^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,\mbox{$w$ tem número ímpar de {\tt 0}s e não tem {\tt 0}s
				      consecutivos}\}$.
       \end{list}

\vfill
\hfill {\footnotesize \emph{Segue no verso}} $\Rightarrow$
\pagebreak
 \item (3 pontos) Encontre um AFD equivalente ao AFN:
       \begin{center}
       \begin{picture}(65,40)
        \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
				        fillgray=0.9, loopdiam=4}

%        \put(30,0){\makebox(0,0){\textbf{(b) AFN 2.}}}
        \node[Nmarks=i, iangle=180](1)(10,25){1}
        \node(2)(25,35){2}
        \node[Nmarks=i, iangle=225](3)(25,15){3}
        \node[Nmarks=ir, iangle=0](4)(40,25){4}

        \drawloop[loopangle=90](1){{\tt 0},{\tt 1}}
        \drawedge(1,2){\tt 0}
        \drawedge(1,3){\tt 1}
        \drawedge(2,4){\tt 1}
        \drawedge(3,4){{\tt 0},{\tt 1}}
       \end{picture}
       \end{center}
	\item(3 pontos) Obtenha um AFN que reconheça $\{{\tt bab}\}^*\{{\tt aa},{\tt b}\}^*$. \emph{Sugestão}: Construa
	      um AFN$\lambda$ e, em seguida, retire a(s) transição(ões) $\lambda$.
\end{enumerate}

\end{document}
