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

\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,\{1,2,3\})$ com o diagrama de estados:

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

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

         \drawedge[curvedepth=0](1,2){${\tt 0}/\sqcup$ {\sf E}}
         \drawloop[loopangle=0](2){\shortstack{$\langle/\langle$ {\sf D} \\
                                                 $\sqcup/\sqcup$ {\sf E}}}
         \drawedge[curvedepth=0](1,3){${\tt 1}/\sqcup$ {\sf D}}
         \drawloop[loopangle=180](3){${\tt 1}/\sqcup$ {\sf D}}
         \drawedge[curvedepth=0](3,4){$\sqcup/\sqcup$ {\sf E}}
        \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 $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,n_{\tt a}(w)>n_{\tt b}(w)\}$.
	      ($n_{\tt a}(w)$: número de {\tt a}s na palavra $w$.)

 \item No curso, foi mostrado como construir em três passos, a partir de uma MT $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i,F)$,
       uma gramática que gera $L(M)$. Mostre regras para o primeiro passo, em que é gerada toda forma sentencial
			 $w\langle i w \rangle$ a partir do símbolo de partida $P$. Nesta forma sentencial, $\langle$, $i$ e $\rangle$ são
			 variáveis e $w\in\Sigma^*$.

 \item Mostre que para um autômato de pilha $P$ e uma expressão regular $r$ arbitrários:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item É decidível determinar se $L(P)\subseteq L(r)$.
				\item É indecidível determinar se $L(r)\subseteq L(P)$.
       \end{list}

 \item Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma gramática irrestrita $G$, determinar se $L(G)\not=\emptyset$.
        \item Dada uma MT, determinar se ela lê {\tt 0} em algum momento para a entrada $\lambda$ (fita em branco).
       \end{list}
\end{enumerate}

\end{document}
