\documentclass[11pt,a4paper]{book}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{10mm}
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}/DINTER
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Prova Suplementar} \hfill 10/12/2010

\vspace*{3mm}
\begin{flushleft}
Dura\c{c}\~ao: 1 hora e 40 minutos.
\end{flushleft}

\vspace{2mm}
\begin{enumerate}
% \item Apresente o diagrama de estados de um AFD que reconheça a linguagem: $$\{w\in \{{\tt 0},{\tt 1}\}^*\,|\,
%       w \mbox{ contém {\tt 1} e não contém {\tt 000}}\}\mbox{.}$$

 \item Sejam as linguagens $L_1=\{w\in \{{\tt a},{\tt b}\}^*\,|\, w \mbox{ tem número par de {\tt a}s}\}$ e 
       $L_2=\{{\tt b}{\tt a}^n\,|\,  n\geq 0\}$. Obtenha um AFD que reconheça $L_1L_2$.

 \item Obtenha uma expressão regular que denote a linguagem reconhecida pelo autômato finito a seguir,
       mostrando os diagramas ER obtidos após a eliminação de cada estado. Expressões regulares com sintaxe incorreta
       acarretarão perda de pontos.

        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,15)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=5}

          \node[Nmarks=ir](1)(40,5){1}
          \node(2)(60,5){2}
          \node(3)(80,5){3}

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

 
 \item Apresente diagramas de estados para AFNs que reconhe\c{c}am as seguintes linguagens, ambas de
       alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{itemize}
        \item O conjunto das palavras em que o terceiro e o quinto símbolos da direita para a esquerda são
              {\tt 0}.
        \item O conjunto das palavras com pelo menos duas ocorrências de {\tt 010} em que há um número
              ímpar de símbolos entre duas ocorrências de {\tt 010}.
       \end{itemize}

 \item Prove que $\{{\tt a}^k{\tt b}^n \,|\, n\leq k\leq 2n\}$ não é uma linguagem regular.
 
 \item Para cada PD abaixo, mostre que o mesmo \'e decid\'{\i}vel ou que n\~ao \'e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Dadas uma máquina de Turing $T$ e um autômato finito $A$, determinar se $L(A)\cap L(T)\not=\emptyset$.
        \item Dada uma máquina de Turing $T$, determinar se $|L(T)|>n$, sendo n o número de estados de $M$.
        \item Dado um número $n\geq 0$, determinar se existe uma MT $T$ talque ${\tt 0}^n\in L(T)$.
        \item Dado um número $n\geq 0$ e uma MT $T$, determinar se ${\tt 0}^n\in L(T)$.
       \end{list}
\end{enumerate}

\end{document}