\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Lista de Exercícios Preparatória para a Terceira Prova}

\vspace*{3mm}
\begin{enumerate}
 \item Seja a gram\'atica:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, P A A  \,|\,  B \,|\, A {\tt b} \,|\, CD$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, B \,|\, BC$
	      \item[\ ] $B\,\rightarrow\,\lambda$
	      \item[\ ] $C\,\rightarrow\, BC$
	      \item[\ ] $D\,\rightarrow\, {\tt b}D \,|\, {\tt bb}$
	     \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se existirem s\'{\i}mbolos in\'uteis, elimine-os.
        \item Elimine regras $\lambda$.
        \item Elimine regras unit\'arias.
        \item Obtenha uma GLC equivalente na forma normal de Chomsky.
       \end{list}

 \item Mostre que s\~ao ou que n\~ao s\~ao linguagens livres do contexto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+,\verb+c+\}^* \,|\, n_a(w)<n_b(w)\}$.
        \item $\{w\in\{\verb+a+,\verb+b+,\verb+c+\}^* \,|\, n_a(w)<n_b(w) \mbox{ ou } n_a(w)<n_c(w)\}$.
        \item $\{w\in\{\verb+a+,\verb+b+,\verb+c+\}^* \,|\, n_a(w)<n_b(w)<n_c(w)\}$.
       \end{list}
       Aqui $n_s(w)$ \'e a quantidade do s\'{\i}mbolo {\tt s} na palavra $w$.

 \item Prove que as seguintes afirmativas s\~{a}o ou n\~ao verdadeiras, considerando
       os casos em que (i) $X$ \'e finita e (ii) $X$ \'e regular.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'{e} uma LLC, ent\~{a}o $L-X$ \'{e} uma LLC.
        \item Se $L$ n\~{a}o \'{e} uma LLC, ent\~{a}o $L-X$ n\~{a}o \'{e} uma LLC.
       \end{list}

 \item Crie MTs padrão que reconhe\c cam as seguintes linguagens de alfabeto $\{{\tt a},{\tt b},{\tt c}\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item ${\tt a}^*$.
        \item $\{{\tt a}^n{\tt b}^n\,|\, n\geq 0\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^{m+n}\,|\, m,n\geq 0\}$.
       \end{list}

 \item Faça uma MT de duas fitas que reconheça $\{{\tt a}^m{\tt b}^n{\tt c}^{m+n}\,|\, m,n\geq 0\}$.

 \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 que gerem:
       \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 que reconheça $\{ww \,|\, w\in\{{\tt a},{\tt b}\}^+\}$.

 \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 duas fitas e não
       determinismo.

 \item Um problema de decisão $PD$ tem solução se para cada instância $p\in PD$ existe uma MT que, recebendo $p$ como
       entrada, determina a resposta correta para $p$. Que relação existe entre decidibilidade (de problemas de decisão)
       e classes de linguagens reconhecíveis por MTs?


\end{enumerate}

\end{document}
