\documentclass[11pt,a4paper]{book}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\newcounter{conta2}
\pagestyle{empty}

\begin{document}
 
\vspace*{10mm}
\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 2011 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Prova Suplementar} \hfill 06/12/2011

\vspace*{3mm}
\begin{flushleft}
Dura\c{c}\~ao: 1 hora e 40 minutos.
\end{flushleft}

\begin{enumerate}
 \item (5 pontos) Responda sem justificar:

       \begin{tabular}{cl||cl}
        (a) & Sejam $A=\{\lambda,\verb+a+\}$ e $B=\{\verb+a+,\verb+b+\}$. Quantos & (b) & Simplifique: \\
            & elementos tem:                        &    & \ \ \ $(A^*)^+$ \\
            & \ \ \ $AB$                            &    & \ \ \ $(A^+)^*$ \\
            & \ \ \ $A^nB$                          &    & \ \ \ $A^*\cap A^+$ \\
            & \ \ \ $AB^n$                          &    & \ \ \ $A^*A^+$ \\
            & \ \ \ $A^nB^n$                        &    & \ \ \ $A^+-A^*$ \\
            & para $n\geq 0$ arbitr\'ario?          &    & \ \ \ $A^*-A^+$
       \end{tabular}
 \item (6 pontos) Prove que a linguagem
      \[L=\{xy \,\,|\,\, x,y\in\{\verb+a+,\verb+b+\}^* \mbox{ e } |x|=|y|
        \mbox{ e } n_{\verb+a+}(x)=n_{\verb+b+}(y)\}\]
       n\~ao \'e linguagem regular:\footnote{$n_s(w)$ \'e o n\'umero de
       ocorr\^encias do s\'{\i}mbolo $s$ na palavra $w$.}

 \item (5 pontos) Obtenha express\~oes regulares que denotem as linguagens abaixo.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\,$ as posi\c c\~oes pares
                  de $w$ s\'o cont\^em \verb+a+'s e as \'{\i}mpares s\'o cont\^em
                  \verb+b+'s$\}$.
        \item $\{w\verb+a+\in\{\verb+a+,\verb+b+,\verb+c+\}^*\,\,|\,\, w
                    \mbox{ n\~ao cont\'em a subpalavra } \verb+abc+\}$.
       \end{list}


 \item (5 pontos) O seguinte aut\^omato de pilha determin\'{\i}stico reconhece a linguagem dos par\^enteses
       balanceados:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,10)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=ir](1)(50,5){}
         \drawloop[loopangle=0](1){\shortstack{${\tt (}, \lambda/{\tt X}$ \\
                                               ${\tt )}, {\tt X}/\lambda$}}
        \end{picture}
       } \\

       Construa uma MT de duas fitas que reconhe\c{c}a tal linguagem simulando a pilha
       na segunda fita.

 \item (6 pontos) Os problemas abaixo s\~ao indecid\'{\i}veis:
       \begin{enumerate}
        \item[(a)] Dada uma máquina de Turing $M$ verificar se $L(M)$ cont\'em mais de uma palavra.
        \item[(b)] Dados uma máquina de Turing $M$ e uma expressão regular $r$, determinar se $L(M)\subseteq L(r)$.
        \item[(c)] Dados uma máquina de Turing $M$ e um estado $e$, determinar se
                   o estado $e$ \'e alcan\c cado, caso $M$ receba $\lambda$ como entrada.
       \end{enumerate}
       Para quais deles se pode usar o Teorema de Rice? Se para algum deles n\~ao
       for poss\'{\i}vel usar o Teorema de Rice, escolha um e use redu\c c\~ao
       para provar que ele  \'e indecid\'{\i}vel.
\end{enumerate}

\end{document}