\documentclass[11pt,a4paper]{report}

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

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

\pagestyle{empty}
\newcounter{conta}

\begin{document}
 
\vspace*{1cm}
\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 2013 \\
Professor: Newton José Vieira \\
\noindent{\em Primeira prova}    \hfill 19/9/2013

\vspace*{3mm}
\noindent As 4 primeiras questões valem 6 pontos e as duas últimas valem 5 pontos cada uma.
\begin{enumerate}
 \item  Seja a linguagem $L=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, {\tt 00} \mbox{ é subpalavra de } w \mbox{ e }
        {\tt 11} \mbox{ não é subpalavra de } w\}$. Faça:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um AFD que reconheça $L$.
        \item Uma expressão regular que denote $L$.
       \end{list}
 \item Obtenha gramáticas para as seguintes linguagens sobre $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A linguagem da questão anterior.
        \item $\{{\tt 0}^n{\tt 1}^{n}{\tt 0}^n\,|\, n\geq 0\}$.
       \end{list}
 \item Seja a linguagem $X$ denotada por $0+11^*$. Construa autômatos finitos sem transições $\lambda$, que reconheçam $X$,
       com a seguinte característica:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O autômato tem um único estado inicial.
        \item O autômato tem um único estado final.
       \end{list}
 \item Seja o AFN$\lambda$ com o diagrama de estados:

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

         \node[Nmarks=ir](1)(20,10){1}
         \node(2)(40,10){2}
         \node(3)(60,10){3}
         \node[Nmarks=r](4)(80,10){4}

         \drawedge[curvedepth=4](1,2){{\tt 0}}
         \drawedge[curvedepth=4](2,1){{\tt 1}}
         \drawedge[curvedepth=4](3,4){{\tt 1}}
         \drawedge[curvedepth=4](4,3){{\tt 0}}
         \drawedge[curvedepth=-12, ELside=r](1,3){$\lambda$}

         \drawloop[loopangle=90, ELside=l](1){{\tt 0}}
         \drawloop[loopangle=0, ELside=l](4){{\tt 1}}
        \end{picture}
       } \\
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Apresente o diagrama de estados de um AFN equivalente (use o método visto no curso).
        \item Apresente um AFD equivalente.
       \end{list}
 \item Seja $L$ uma linguagem regular sobre o alfabeto $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$. Mostre que a linguagem 
       $\{w\in\Sigma^*\,|\, \mbox{ ou } w\in L\mbox{ ou } w \mbox{ contém pelo menos um  {\tt a} (mas
       não ambos)}\}$ é regular.
 \item Prove que $\{xy\in\{a,b\}^*\,|\, |x|=|y|$ e $n_a(x)\geq n_b(y)\}$ não é regular. ($n_s(w)$ é o número de
       símbolos $s$ na palavra $w$.)

\end{enumerate}

\end{document}
