\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 2013 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Terceira Prova} \hfill 26/11/2013

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

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

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

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

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

       Expresse a linguagem reconhecida por $M$ por meio de uma expressão regular.

  \item Construa uma MT que reconheça $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,n_{\tt 0}(w)>
       n_{\tt 1}(w)\}$. Pode usar mais de uma fita, não determinismo etc.

 \item Dada uma gramática irrestrita $G$, como seria uma MT $M$ que reconhece L(G)? Basta mostrar
       um algoritmo, em alto nível, de $M$. \textit{Dica:} faça, como visto no curso, uma MT não determinística de
			 duas fitas, a primeira contendo a palavra a reconhecer e a segunda uma forma sentencial de $G$.

 \item Faça uma gramática sensível ao contexto que gere a linguagem $\{wxw\,|\, w\in\{{\tt a},{\tt b}\}^*
       \mbox{ e } x\in\{{\tt c}\}^+ \}$.

 \item Seja $L=\{R\langle M\rangle\,|\, L(M)=\{{\tt 00},{\tt 01},{\tt 10},{\tt 11}\}\}$.
       Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L$ é recursivamente enumerável.
				\item $L$ não é recursiva.
       \end{list}

 \item Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma MT, determinar se ela volta ao seu estado inicial se executada com a fita em branco.
        \item Dada uma GLC $G$ e uma gramática regular $H$, determinar se $L(G)=L(H)$.
       \end{list}
\end{enumerate}

\end{document}
