\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: 08/07/2010

\begin{enumerate}

 \item Construa uma MT que, recebendo como entrada uma palavra $w\in\{{\tt 0},{\tt 1}\}^*$, escreva
       no seu lugar a palavra constituída apenas dos {\tt 1}s (os {\tt 0}s devem ser apagados).

 \item Crie uma MT que reconhe\c ca a linguagem denotada pela ER $a(a+b)^*$,
       assumindo que o alfabeto \'e $\{{\tt a},{\tt b}\}$, de forma que ela
       tenha:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item um n\'umero m\'{\i}nimo de estados;
        \item um n\'umero m\'{\i}nimo de transi\c c\~oes.
       \end{list}

 \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 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$? Explique porque.

 \item Fa\c ca uma MT que reconhe\c ca a linguagem $\{wxw\in\{{\tt a},{\tt b}\}^*\,|\, |x|=|w|\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item de duas fitas determin\'{\i}stica;
        \item de duas fitas n\~ao determin\'{\i}stica.
       \end{list}

 \item Construa gram\'aticas irrestritas (GIs) que gerem as linguagens:
       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^{m}{\tt b}^n{\tt a}^{m}{\tt b}^n \,|\, m,n\geq 0\}$.
        \item $\{ww \,|\, w\in\{{\tt a},{\tt b}\}^*\}$.
       \end{list}

 \item Construa uma gram\'atica sens\'{\i}vel ao contexto (GSC) para a linguagem
       \[\{{\tt a}^m{\tt b}^n{\tt c}^k\,\,|\,\,m<n<k\}\mbox{.}\]
       Procure obter uma GSC com um n\'umero m\'{\i}nimo de regras.
\pagebreak
 \item Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item $L\cup F$ n\~ao \'e recursiva, se $F$ \'e finita.
        \item $\overline{L}$ n\~ao \'e recursiva.
        \item Se $L$ \'e LRE, ent\~ao $\overline{L}$ n\~ao \'e LRE.
       \end{list}

 \item Mostre que as LREs s\~ao fechadas sob concatena\c c\~ao por meio de MTs.
       {\em Dica\/}: Use {\em n\~ao\/} determinismo.

 \item Seja $\Sigma=\{{\tt 0},{\tt 1}\}$. Considerando que o conjunto de todas as MTs de alfabeto de entrada
       $\Sigma$ \'e enumer\'avel, mostre que existe uma linguagem, subconjunto de $\Sigma^*$, que n\~ao \'e LRE.
       Para isso, use o argumento da diagonaliza\c c\~ao de Cantor (veja a p\'agina 25 do livro-texto).

\end{enumerate}

\end{document}
