\documentclass[12pt, a4paper]{report}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\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: 11/03/03

\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 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 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.
