\documentclass[12pt, a4paper]{report}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2002
 
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG
 
\noindent {\bf Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: 23/09/02 (M), 24/09/02 (A)

\begin{enumerate}

 \item Construa uma MT com alfabeto de entrada $\{\verb+a+\}$ que pare se, e somente se, a palavra
       de entrada for da forma $\verb+a+^{2n}$ para $n\geq 0$.

 \item Construa MT's (de qualquer um dos tipos abordados, inclusive combinados) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^{2n}\verb+1+^n\,\,|\,\, n\geq 0\}$
        \item $\{\verb+a+^m\verb+b+^n\,\,|\,\, m\not=n\}$
        \item $\{xx\,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$
        \item $\{xx^Ry\,\,|\,\,x,y\in\{\verb+0+,\verb+1+\}^* \mbox{ e } |x|>|y|\}$
        \item $\{\verb+a+^n\,\,|\,\, n \mbox{ n\~ao \'e primo}\}$
       \end{list}
       Procure obter um m\'{\i}nimo de transi\c c\~oes poss\'{\i}vel.

 \item Seja a linguagem dos par\^enteses balanceados, que \'e gerada pela gra\-m\'a\-ti\-ca
       $(\{P\},\{\verb+(+,\verb+)+\},R,P)$, onde $R$ consta das regras:
       \begin{enumerate}
        \item[\ ] $P\,\,\rightarrow\,\, \lambda \,\,|\,\, \verb+(+ P \verb+)+ P$
       \end{enumerate}
       Construa uma MT que reconhe\c ca tal linguagem.

 \item Mostre como construir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Uma MT que reconhece por parada em estado final equivalente a uma que reconhece por estado final.
        \item Uma MT que reconhece por estado final equivalente a uma que reconhece por parada.
        \item Uma MT que reconhece por parada equivalente a uma MT que reconhece por parada em estado final.
       \end{list}

 \item Construa uma MT que reconhe\c ca a linguagem: \[\{\verb+0+^{k_0}\verb+1+\verb+0+^{k_1}\verb+1+
       \ldots\verb+0+^{k_n}\verb+1+\,\,|\,\,n\in\mbox{\bf N} \mbox{ e }
       0<k_0<k_1<\cdots<k_n\}\mbox{.}\]
       Use uma fita s\'o para assegurar a restri\c c\~ao $0<k_0<k_1<\cdots<k_n$.

 \item Seja a MT n\~ao determin\'{\i}stica \[M=(\{a,b,c,d\},\{0,1\},\{\langle,\sqcup,0,1\},\langle,
       \sqcup, \delta,\{a\},\{b\})\mbox{,}\] onde $\delta$ \'e assim definida:
       \begin{enumerate}
        \item[\ ] $\delta(a,0)=\{[b,0,D],[d,0,D]\}$
        \item[\ ] $\delta(b,0)=\{[c,0,E]\}$
        \item[\ ] $\delta(c,0)=\{[b,0,D]\}$
        \item[\ ] $\delta(d,0)=\{[d,0,D]\}$
        \item[\ ] $\delta(d,\sqcup)=\{[b,0,D]\}$
       \end{enumerate}
       Que linguagem \'e reconhecida por $M$?

 \item Construa uma GSC que gere e um ALL que reconhe\c ca a linguagem
       \[\{\verb+a+^m\verb+b+^n\verb+c+^k\,\,|\,\,m>n>k\}\mbox{.}\]

 \item Construa gram\'aticas irrestritas que gerem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+^k\verb+0+^n\verb+1+^k\,\,|\,\, n,k\geq 0\}$
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^k\,\,|\,\, m<n<k\}$
        \item $\{www\,\,|\,\,w\in\{\verb+0+,\verb+1+\}^*\}$
       \end{list}

 \item A linguagem $\{ww\,\,|\,\,w\in\{\verb+0+,\verb+1+\}^+\}$ \'e uma LSC? Por que?

 \item Seja $L$ uma LRE de alfabeto $\Sigma$, e $\#$ um s\'{\i}mbolo n\~ao pertencente
       a $\Sigma$. Mostre que existe uma LSC $L'$ de alfabeto $\Sigma\cup\{\#\}$ tal que,
       para todo $w\in \Sigma^*$:
       \[w\in L \mbox{ se, e somente se, } w\#^k\in L' \mbox{ para algum $k\geq 0$.}\]

 \item Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\overline{L}$ n\~ao \'e recursiva.
        \item Se $L$ \'e LRE, ent\~ao $\overline{L}$ n\~ao \'e LRE.
       \end{list}

 \item Sejam $L$ uma LRE e $R$ uma linguagem recursiva.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $L-R$ \'e uma LRE.
        \item $L-R$ \'e recursiva?
        \item $R-L$ \'e LRE?
       \end{list}


\end{enumerate}

\end{document}


 \item Construa uma MT padr\~ao que gere todos os n\'umeros naturais em nota\c c\~ao
       bin\'aria. A MT n\~ao deve parar nunca. Ela gerar \verb+0+, depois \verb+1+, depois
       \verb+10+, etc., separados por branco, indefinidamente. A fita dever\'a ficar assim:
       \[\langle\verb+0+\sqcup\verb+1+\sqcup\verb+10+\sqcup\verb+11+\sqcup\verb+100+
         \sqcup\verb+101+\sqcup\verb+110+\sqcup\cdots\]

 \item Construa uma MT com alfabeto de entrada $\{\verb+0+,\verb+1+\}$, que interprete a
       palavra de entrada como a representa\c c\~ao bin\'aria de um n\'umero natural e
       determine a representa\c c\~ao un\'aria de tal n\'umero. Pode usar qualquer modelo
       de MT; em particular, pode usar uma fita s\'o para conter o resultado.

 \item Construa uma MT com fita ilimitada em ambas as dire\c c\~oes que, come\c cando a
       fita com duas c\'elulas contendo o s\'{\i}mbolo \verb+1+ e o resto branco, determine
       se o n\'umero de brancos entre os dois \verb+1+'s \'e \'{\i}mpar, e, neste caso,
       pare em estado de aceita\c c\~ao. Observe que os dois s\'{\i}mbolos referidos pode
       estar em {\em qualquer lugar\/} da fita.

 \item Completar o esbo\c co apresentado na Se\c c\~ao~\ref{submtmf} para obter uma MT de
       4 trilhas equivalente a uma MT de 2 fitas.

 \item Escreva MT's n\~ao determin\'{\i}sticas que reconhe\c cam as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{xww^Ry\,\,|\,\,x,y,w\in\{\verb+0+,\verb+1+\}^+ \mbox{ e } |x|>|w|>|y|\}$
        \item $\{\verb+0+^n\,\,|\,\, \mbox{$n$ n\~ao \'e primo}\}$
       \end{list}

 \item Completar o esbo\c co apresentado na Se\c c\~ao~\ref{submtnd} para obter uma MT
       determin\'{\i}stica de 3 fitas equivalente a uma MT n\~ao determin\'{\i}stica.

 \item Uma MT multicabe\c cote \'e uma MT padr\~ao com v\'arios cabe\c cotes independentes,
       mas uma \'unica fita. Fa\c ca uma defini\c c\~ao formal de tal tipo
       de m\'aquina. Mostre como simul\'a-la mediante uma MT padr\~ao.

 \item Uma MT bidimensional \'e uma MT cuja fita tem duas dimens\~oes, ou seja, \'e uma
       matriz bidimensional que se estende indefinidamente em duas dire\c c\~oes. Com isto,
       existem mais duas  possibilidades de movimenta\c c\~ao para o cabe\c cote, al\'em de
       {\em direita\/}, {\em esquerda\/} e {\em im\'ovel\/}: {\em para cima\/} e {\em para
       baixo\/}. Fa\c ca uma defini\c c\~ao formal de MT bidimensional. Em seguida, mostre
       como simular uma MT bidimensional por meio de algum outro tipo de MT que voc\^e
       conhece.

 \item Construa um ALL que aceite $\{\verb+a+^{n!}\,\,|\,\,n\geq 0\}$. {\em Sugest\~ao\/}:
       Divida a palavra de entrada por $2, 3, 4, \ldots, n$. Use duas trilhas,
       uma das quais para conter os divisores $2, 3, 4, \ldots$

 \item Mostre que toda LSC pode ser reconhecida por um ALL.

       \label{elscall}

 \item Mostre que $L(M)-\{\lambda\}$ \'e LSC, caso $M$ seja um ALL.

       \label{ealllsc}

 \item Mostre que as LSC's s\~ao fechadas ou n\~ao sob:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Uni\~ao.
        \item Concaten\c c\~ao.
        \item Fecho de Kleene.
       \end{list}

 \item Seja $\{L_1,L_2,\ldots,L_n\}$, $n\geq 2$, uma parti\c c\~ao de $\Sigma^*$, onde
       $\Sigma$ \'e um alfabeto. Mostre que se cada $L_i$ \'e uma LRE, ent\~ao cada $L_i$
       \'e uma linguagem recursiva.

 \item Seja $L$ uma LRE n\~ao recursiva e $M$ uma MT que reconhece $L$. Seja
       \[S=\{w\in\overline{L}\,\,|\,\, M \mbox{ entra em {\em loop\/} se a entrada \'e $w$}\}\mbox{.}\]
       Mostre que $S$ \'e infinito.

 \item Sejam $L_1,L_2,\ldots$ LRE's. Mostre que $\cup_{i\geq 1}L_i$ \'e LRE ou que n\~ao \'e.

 \item Mostre que as LRE's s\~ao fechadas sob concatena\c c\~ao e fecho de {\em Kleene\/} por meio de
       gram\'aticas. (Cuidado! As t\'ecnicas simples usadas para GLC's n\~ao funcionam aqui sem
       adapta\c c\~oes!)

 \item Seja $L$ uma LRE que n\~ao seja recursiva. Mostre que para qualquer MT que reconhe\c ca $L$,
       o conjunto das palavras de entrada para as quais $M$ n\~ao p\'ara \'e infinito.

 \item Prove que toda LSC pode ser gerada por uma gram\'atica na qual cada regra tem a forma
       $x A y\rightarrow x w y$, onde $w\in (V\cup\Sigma)^+$ e $x,y\in (V\cup\Sigma)^*$.
       {\em Sugest\~ao\/}:
       primeiramente, mostre que para toda GSC existe uma GSC equivalente em que cada regra
       tem um lado direito com, no m\'aximo, dois s\'{\i}mbolos. Em seguida, mostre como obter
       o mesmo efeito de uma regra da forma $AB\rightarrow CD$ apenas com regras da forma 
       $x A y\rightarrow x w y$.

       \label{efngsc}

\end{enumerate}
