\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 Prova Suplementar/Solução do professor}

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

 \item {\footnotesize Determine uma expressão regular que denote o complemento de $\{{\tt 01}\}^*$ da seguinte
       forma:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Desenhe o diagrama de estados de um autômato finito determinístico de 3 estados que reconheça
				      $\{{\tt 01}\}^*$.
				\item A partir desse autômato, obtenha um outro que reconheça o complemento de  $\{{\tt 01}\}^*$.
				\item A partir desse último, explicite um diagrama de expressões regulares (diagrama ER) a ser usado como
				      ponto de partida para a obtenção de uma expressão regular.
				\item Obtenha a expressão regular, a partir do diagrama ER, por meio do método de eliminações sucessivas de
				      estados.
			 \end{list}}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item AFD para $\{{\tt 01}\}^*$:
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(180,40)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

                \node[Nmarks=ir](1)(30,30){1}
                \node(2)(60,30){2}
                \node(3)(45,15){3}

                \drawedge[curvedepth=3](1,2){\tt 0}
                \drawedge[curvedepth=0, ELside=r](1,3){\tt 1}
                \drawedge[curvedepth=3](2,1){\tt 1}
                \drawedge[curvedepth=0](2,3){\tt 0}

                \drawloop[loopangle=270, ELside=l](3){\tt 0,1}
               \end{picture}
              }
         \item AFD para $\overline{\{{\tt 01}\}^*}$:
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(180,40)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

                \node[Nmarks=i](1)(30,30){1}
                \node[Nmarks=r](2)(60,30){2}
                \node[Nmarks=r](3)(45,15){3}

                \drawedge[curvedepth=3](1,2){\tt 0}
                \drawedge[curvedepth=0, ELside=r](1,3){\tt 1}
                \drawedge[curvedepth=3](2,1){\tt 1}
                \drawedge[curvedepth=0](2,3){\tt 0}

                \drawloop[loopangle=270, ELside=l](3){\tt 0,1}
               \end{picture}
              }
         \item Diagrama ER inicial:
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(180,40)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

                \node[Nmarks=i](1)(30,30){1}
                \node[Nmarks=r](2)(60,30){2}
                \node[Nmarks=r](3)(45,15){3}

                \drawedge[curvedepth=3](1,2){$0$}
                \drawedge[curvedepth=0, ELside=r](1,3){$1$}
                \drawedge[curvedepth=3](2,1){$1$}
                \drawedge[curvedepth=0](2,3){$0$}

                \drawloop[loopangle=270, ELside=l](3){$0+1$}
               \end{picture}
              }
         \item Mantendo-se o estado final 2 e eliminando-se 3:
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(70,20)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

                \node[Nmarks=i](1)(30,10){1}
                \node[Nmarks=r](2)(60,10){2}

                \drawedge[curvedepth=3](1,2){$0$}
                \drawedge[curvedepth=3](2,1){$1$}
               \end{picture}
							  ER $r_1: 0(10)^*$.
              }

              Mantendo-se o estado final 3 e eliminando-se 2:
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(70,30)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

                \node[Nmarks=i](1)(30,10){1}
                \node[Nmarks=r](3)(60,10){3}

                \drawloop[loopangle=90, ELside=l](1){$01$}
                \drawedge[curvedepth=0](1,3){$1+00$}
                \drawloop[loopangle=90, ELside=l](3){$0+1$}
               \end{picture}
							  ER $r_2: (01)^*(1+00)(0+1)^*$.
              }

             ER para o complemento de $\{01\}^*$: $r_1+r_2=0(10)^*+(01)^*(1+00)(0+1)^*$.
			 \end{list}

 \item {\footnotesize Diga se é verdade ou falso, \underline{justificando}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Se $L_1$ e $L_2$ são linguagens livres do contexto e $L_1\subseteq L_2$, então $L_2-L_1$ é uma linguagem
				      livre do contexto.
				\item Uma gramática $(V,\Sigma,R,P)$ em que cada regra é da forma $X\rightarrow w$, sendo $X\in V$,
				      $w\in (V\cup\Sigma)^*$ e $|w|\leq 2$, pode gerar qualquer linguagem livre do contexto.
			 \end{list}}

      \textit{Solu\c{c}\~ao\/}: 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Falso. $\Sigma^*$ é livre do contexto e se $L$ for livre do contexto, $\Sigma^*-L$ pode não ser livre do
						 contexto, visto que a classe das linguagens livres do contexto não é fechada sob complementação.
				\item Verdadeiro. Uma gramática na forma normal de Chomsky só tem regras dessa forma.
			 \end{list}}

 \item {\footnotesize Mostre que são equivalentes os seguintes critérios de aceitação para máquinas de Turing:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Por estado final: uma palavra $w$ é aceita se e somente se a máquina atinge algum estado final
				      ao processar $w$,.
				\item Por parada: uma palavra $w$ é aceita se e somente se a máquina para ao processar $w$.
			 \end{list}}

       \textit{Solu\c{c}\~ao\/}: 
       
			 (a)$\rightarrow$(b)
				
	     Seja $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i,F)$ uma MT que aceite por estado final. Então a MT
			 $(E\cup\{l\},\Sigma,\Gamma,\langle,\sqcup,\delta',i)$ tal que
			 \begin{itemize}
			  \item $l\not\in E$;
				\item $\delta'(l,a)=[l,a,D]$ para todo $a\in\Gamma$;
				\item $\delta'(e,a)$ é indefinido para todo $(e,a)\in F\times\Gamma$;
				\item $\delta'(e,a)=\delta(e,a)$ para todo $(e,a)\in (E-F)\times\Gamma$ tal que $\delta(e,a)$ é definido;
				\item $\delta'(e,a)=[l,a,D]$ para todo $(e,a)\in (E-F)\times\Gamma$ tal que $\delta(e,a)$ é indefinido;
			 \end{itemize}
			 aceita $L(M)$ por parada. \\

			 (b)$\rightarrow$(a)
				
	     Seja $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i)$ uma MT que aceite por parada. Então a MT
			 $(E\cup\{f\},\Sigma,\Gamma,\langle,\sqcup,\delta',i,\{f\})$ tal que
			 \begin{itemize}
			  \item $f\not\in E$;
				\item $\delta'(e,a)=\delta(e,a)$ para todo $(e,a)\in E\times \Gamma$ tal que $\delta(e,a)$ é definido;
				\item $\delta'(e,a)=[f,a,D]$ para todo $(e,a)\in E\times \Gamma$ tal que $\delta(e,a)$ é indefinido;
			 \end{itemize}
			 aceita $L(M)$ por estado final.

 \item {\footnotesize Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma GLC $G$, determinar se $L(G)\cap \{1\}^*\not=\emptyset$.
        \item Dada uma MT, determinar se todos os seus estados são úteis. Estado útil: aquele que é atingido
				      durante o processamento de alguma palavra de entrada.
       \end{list}}

       \textit{Solu\c{c}\~ao\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Decidível. Tal problema pode ser reduzido ao problema decidível de determinar, dada uma GLC $H$, se 
				     $L(H)\not=\emptyset$: pode-se obter uma GLC $H$ tal que $L(H)=L(G)\cap \{1\}^*$, como visto
				      quando se mostrou que as linguagens livres do contexto são fechadas sob interseção com linguagens regulares.
        \item Indecidível. O problema da parada para a fita em branco pode ser reduzido a este produzindo-se,
				      a partir de $R\langle M\rangle$, em que $M=(\{e_1,\ldots,e_n\},\Sigma,\Gamma,\langle,\sqcup,\delta,i)$, uma MT
							$M'=(\{e_1,\ldots,e_n,q\}\cup X,\Sigma,\Gamma\cup\{c\},\langle,\sqcup,\delta',i')$ tal que:
							\begin{itemize}
							 \item $i'\in X$ e $X\cap\{{e_1,\ldots,e_n,q\}=\emptyset$;
							 \item $q\not\in \{e_1,\ldots,e_n\}$;
							 \item Usando os estados em $X$, $M'$ apaga a entrada e transita para $i$ com o cabeçote posicionado no início.
							 \item $c\not\in\Gamma$;
							 \item $\delta'(e,a)=\delta(e,a)$ para todo $(e,a)\in E\times\Gamma$ tal que $\delta(e,a)$ é definido;
							 \item $\delta'(e,a)=[q,c,I]$ para todo $(e,a)\in E\times\Gamma$ tal que $\delta(e,a)$ é indefinido;
							 \item $\delta(e_i,c)=[e_{i+1},c,I]$ para $1\leq i<n$;
							 \item $\delta(e_n,c)$ é indefinido.
							\end{itemize}
							Com isto, $M$ para se processar com a fita em branco sse $M'$ atinge o estado $q$ ao processar sua entrada,
							qualquer que ela seja, sse todos os estados de $M'$ são visitados sse todos os estados de $M'$ são úteis.
       \end{list}
\end{enumerate}

\end{document}
