\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}/Solução do professor \hfill 2/12/2013

\begin{enumerate}

 \item {\footnotesize 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}.}

       \textit{Solução}: $\lambda+11^*0(0+1)^*$

  \item {\footnotesize 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$.)}

       \textit{Solução}: \ 

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

         \node[Nmarks=i](1)(50,5){}
         \node(2)(85,5){}
         \node[Nmarks=r](3)(120,5){}

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

 \item {\footnotesize 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^*$.}

       \textit{Solução}: Sejam $\Sigma=\{a_1,\ldots, a_n\}$ o alfabeto de $M$ (e de terminais da gramática) e
			 $\{A_1,\ldots, A_n\}$ variáveis para a gramática. As regras:
       \begin{quote}
			  $P \,\rightarrow\, B \rangle$ \\
			  $B \,\rightarrow\, a_j B A_j$ para $1\leq j\leq n$ \\
			  $B \,\rightarrow\, \langle i$ \\
			  $a_j A_k \,\rightarrow\, A_k a_j$ para $1\leq j\leq n$ e $1\leq k\leq n$ \\
			  $i A_k \,\rightarrow\, i a_k$ para $1\leq k\leq n$ \\
			 \end{quote}

 \item {\footnotesize 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}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(P)\subseteq L(r)$ sse $L(P)\cap \overline{L(r)}=\emptyset$ sse $L(G)=\emptyset$, onde $G$ é obtido assim:
				      \begin{enumerate}
							 \item de $r$ obtém-se um AFD $M$ tal que $L(M)=L(r)$;
							 \item de $M$ obtém-se um AFD $M'$ tal que $L(M')=\overline{L(M)}$;
							 \item de $P$ e $M'$ obtém-se um AP $P'$ tal que $L(P')=L(P)\cap L(M')$;
							 \item de $P'$ obtém-se uma GLC $G$ tal que $L(G)=L(P')$.
							\end{enumerate}
							Como o problema de determinar se $L(G)=\emptyset$ é decidível, o problema em questão é decidível.
				\item O problema indecidível de determinar se $L(G)=\Sigma^*$, para GLCs $G$,  pode ser reduzido a este
				      produzindo-se uma expressão regular $r$ que denote $\Sigma^*$ e uma GLC $G$ que gere $L(P)$, pois:
							$L(G)=\Sigma^*$ sse $\Sigma^*\subseteq L(G)$.
       \end{list}
 \item {\footnotesize 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}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item É indecidível. O problema de determinar se $L(M)\not=\emptyset$, para MTs $M$, é indecidível (pelo Teorema de
				      Rice). Tal problema pode ser reduzido ao problema em questão produzindo-se uma gramática irrestrita $G$ tal que
							$L(G)=L(M)$.
        \item É indecidível. O problema da fita em branco pode ser reduzido ao problema em questão produzindo-se $M'$ a partir
				      de $M$ tal que $M'$ só difere de $M$ com relação a:
							\begin{itemize}
							 \item se $M$ contém o símbolo {\tt 0}, em $M'$ tal símbolo deve estar substituído por um símbolo diferente de
							       todos aqueles do alfabeto de fita de $M$; e
							 \item nas situações em que $M$ para, $M'$ escreve {\tt 0} e, em seguida, lê o {\tt 0} escrito.
							\end{itemize}
       \end{list}
\end{enumerate}

\end{document}
