\documentclass[11pt,a4paper]{book}

\usepackage[portuguese]{babel}
\usepackage{verbatim}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
%\pagestyle{empty}

\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Prova Suplementar/Solu\c{c}\~ao do professor} \hfill 10/12/2007

%\vspace*{5mm}
%\noindent A \'ultima quest\~ao vale 7 pontos e as restantes 5 pontos.

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Seja a defini\c c\~ao recursiva de {\em reverso\/} de uma palavra sobre $\Sigma$:
       \begin{itemize}
        \item $\lambda^R=\lambda$;
        \item se $x\in\Sigma^*$ e $a\in\Sigma$ ent\~ao $(xa)^R=ax^R$.
       \end{itemize}
       Prove, por indu\c{c}\~ao, que $(xy)^R=y^Rx^R$.}
       
       \textit{Solu\c{c}\~ao}:
       
       Indu\c{c}\~ao sobre $y$. Para $|y|=0$, tem-se que $y=\lambda$ e, assim, $(xy)^R=(x\lambda)^R=x^R=
       \lambda x^R=\lambda^Rx^R=y^Rx^R$. Seja $n\geq 0$ e suponha, como hip\'otese de indu\c{c}\~ao, que
       $(xy)^R=y^Rx^R$ para $|y|=n$. Seja $z$ uma palavra com $n+1$ s\'{\i}mbolos; ent\~ao $z=ya$, onde
       $y\in\Sigma^*$, $a\in\Sigma$ e $|y|=n$. Segue-se que:
       \begin{tabbing}
	      xxxx\=$(xz)^R$ \= $=a(y^Rx^R)$xx \= \kill
	       \> $(xz)^R$ \> $=(x(ya))^R$     \> pois $z=ya$ \\
	       \>          \> $=((xy)a)^R$     \> pela associatividade da concatena\c{c}\~ao \\
	       \>          \> $=a(xy)^R$       \> pela defini\c{c}\~ao de reverso \\
	       \>          \> $=a(y^Rx^R)$     \> pela hip\a'otese de indu\c{c}\~ao \\
	       \>          \> $=(ay^R)x^R$     \> pela associatividade da concatena\c{c}\~ao \\
	       \>          \> $=(ya)^Rx^R$     \> pela defini\c{c}\~ao de reverso \\
	       \>          \> $=z^Rx^R$        \> pois $z=ya$. \\
       \end{tabbing}

 \item {\footnotesize Mostre que sim ou que n\~ao: para todo AFN existe um equivalente com
       um \'unico estado final.}
       
       \textit{Solu\c{c}\~ao}:
       
       Sim. Seja um AFN qualquer $M=(E,\Sigma,\delta,I,F)$ com mais de um estado final. Um AFN
       com um \'unico estado final $f\not\in F$, equivalente a $M$, seria $(E\cup\{f\},\Sigma,\delta',I',\{f\})$,
       em que:
       \begin{itemize}
	      \item se $I\cap F=\emptyset$, ent\~ao $I'=I$, sen\~ao $I'=I\cup\{f\}$; e
	      \item para cada $(e,a)\in E\times\Sigma$: se $\delta(e,a)\cap F=\emptyset$, ent\~ao
	            $\delta'(e,a)=\delta(e,a)$, sen\~ao $\delta'(e,a)=\delta(e,a)\cup\{f\}$;
	            e $\delta'(f,a)=\emptyset$ para todo $a\in\Sigma$.
       \end{itemize}

 \item {\footnotesize Mostre que se $L$ \'e uma linguagem n\~ao regular, ent\~ao a elimina\c{c}\~ao de
       um conjunto finito de palavras da mesma n\~ao \'e suficiente para torn\'a-la regular.}

       \textit{Solu\c{c}\~ao}:
       
       Seja $X$ o conjunto das palavras eliminadas de $L$. Suponha que $L-X$ seja regular. Neste caso,
       como $X$ \'e regular (por ser finito) e as linguagens regulares s\~ao fechadas sob uni\~ao,
       $(L-X)\cup X$ \'e regular. Mas, como $X\subset L$, $(L-X)\cup X=L$, que n\~ao \'e regular.
       Contradi\c{c}\~ao. Logo, $L-X$ n\~ao \'e regular.

 \item {\footnotesize Construa uma gram\'atica livre do contexto para $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m+n>k\}$.}

       \textit{Solu\c{c}\~ao}:
       \begin{enumerate}
        \item[\ ] $P \,\rightarrow\, {\tt a}P{\tt c} \,|\, {\tt a}P \,|\, {\tt a}X \,|\, {\tt b}X$
        \item[\ ] $X \,\rightarrow\, {\tt b}X{\tt c} \,|\, {\tt b}X \,|\, \lambda$
       \end{enumerate}

 \item {\footnotesize Para cada problema, mostre que ele \'e ou que n\~ao \'e decid\'{\i}vel:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Determinar se uma MT, ao iniciar com a fita em branco, chega a ler o s\'{\i}mbolo de
              in\'{\i}cio, $\langle$, em algum momento. 
        \item Determinar se uma gram\'atica regular \'e amb\'{\i}gua.
       \end{list}}

       \textit{Solu\c{c}\~ao}:
       
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Indecid\'{\i}vel. O problema da fita em branco pode ser reduzido a este como segue. A partir de
              uma MT $M$, produz-se uma MT $M'$ tal que:
              \begin{enumerate}
               \item[1.] O s\'{\i}mbolo de in\'{\i}cio de fita de $M'$ \'e diferente do de $M$; seja
                     ``$[$'' o de $M'$ e ``$\langle$'' o de $M$.
               \item[2.] No in\'{\i}cio, $M'$ escreve $\langle$ logo ap\'os seu s\'{\i}mbolo de in\'{\i}cio de fita,
                     $[$, e posiciona o cabe\c{c}ote na posi\c{c}\~ao seguinte.
               \item[3.] Em seguida, $M'$ se comporta como $M$, s\'o que, nas situa\c{c}\~oes em que $M$ p\'ara,
                     $M'$ volta o cabe\c{c}ote at\'e atingir $[$.
              \end{enumerate}
              Desta forma, $M'$ chega a ler o s\'{\i}mbolo de in\'{\i}cio se a entrada for $\lambda$ se,
              e somente se, $M$ p\'ara se a entrada for $\lambda$. Como o problema da fita em branco
              \'e indecid\'{\i}vel e foi reduzido ao problema em quest\~ao, este \'e indecid\'{\i}vel.
        \item Decid\'{\i}vel. Seja $n$ o n\'umero de vari\'aveis da gram\'atica. Considere as deriva\c{c}\~oes de
              tamanho, no m\'aximo, $n$. Se duas delas derivarem a mesma palavra, a gram\'atica \'e amb\'{\i}gua,
              caso contr\'ario, n\~ao \'e amb\'{\i}gua.
       \end{list}
\end{enumerate}

\end{document}