\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 {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2015 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Terceira Prova} \hfill 26/11/2015

\vspace*{3mm}
\begin{enumerate}

 \item Seja a MT $M=(\{1,2,3,4\},\{{\tt 0},{\tt 1}\},\{{\tt 0},{\tt 1},\langle,\sqcup\},
       \langle,\sqcup,\delta,1,\{3,4\})$ com o diagrama de estados:

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

         \node[Nmarks=i](1)(20,15){1}
         \node(2)(40,25){2}
         \node[Nmarks=r](3)(65,25){3}
         \node[Nmarks=r](4)(40,5){4}

         \drawedge[curvedepth=0](1,2){${\tt 0}/\sqcup$ {\sf D}}
         \drawedge[curvedepth=0,ELside=r](1,4){${\tt 1}/{\tt 1}$ {\sf D}}
         \drawloop[loopangle=90](2){${\tt 0}/\sqcup$ {\sf D}}
         \drawedge[curvedepth=0](2,3){$\sqcup/\sqcup$ {\sf E}}
         \drawloop[loopangle=0](4){\shortstack{${\tt 1}/{\tt 1}$ {\sf D} \\
                                                 $\sqcup/\sqcup$ {\sf D}}}
        \end{picture}
       } \\

       Expresse a linguagem reconhecida por $M$ por meio de uma \underline{expressão regular}.

  \item Construa uma MT de duas fitas que reconheça $\{xy\in\{{\tt a},{\tt b}\}^*\,|\,n_{\tt a}(x)>n_{\tt b}(y)\}$.
	      ($n_{\tt a}(w)$: número de {\tt a}s na palavra $w$.) Para facilitar, pode usar não determinismo.

 \item Construa uma gramática que gere $\{{\tt a}^nxx\,|\,x\in\{{\tt a},{\tt b}\}^* \mbox{ e } |x|=n\}$.

 \item Mostre que se o problema da parada fosse decidível, toda linguagem recursivamente enumerável seria recursiva.

 \item Mostre que os seguintes problemas são indecidíveis:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dadas duas gramáticas livres do contexto $G_1$ e $G_2$, cada uma com \emph{uma única variável},
				      determinar se $L(G_1)\cap L(G_2)=\emptyset$.
        \item Dada uma MT $M$ e um símbolo $a$ de seu alfabeto de entrada, determinar se $M$ reconhece alguma palavra que
				      tenha uma ocorrência de $a$.
       \end{list}
\end{enumerate}

\end{document}
