 \documentclass[11pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\pagestyle{empty}
\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill ICEx/UFMG \\
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Exame Especial} \hfill 14/07/2006

\vspace*{3mm}
\begin{enumerate}
 \item (20 pontos) D\^{e} express\~{o}es regulares que
       denotem os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de tamanho \'{\i}mpar sobre $\{{\tt 0},{\tt 1}\}$
              que cont\^{e}m exatamente dois {\tt 1}s.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1},{\tt 2}\}$ que n\~{a}o cont\^{e}m
              {\tt 11}.
       \end{list}

 \item (20 pontos) Mostre que os seguintes conjuntos n\~{a}o s\~{a}o regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n \,|\, m>n\}$.
        \item Conjunto das palavras sobre $\{{\tt a},{\tt b}\}$ em que o n\'umero de {\tt a}s
              \'e maior que o de {\tt b}s.
       \end{list}

 \item (10 pontos) Seja $L$ a linguagem $\{w\in\{{\tt a},{\tt b}\}^*\,|\, 
       w$ tem prefixo contendo mais {\tt b}s que {\tt a}s$\}$. Por exemplo,
       ${\tt baa}, {\tt abba}, {\tt abbaaa}\in L$, mas ${\tt aab}, {\tt aabbab}\not\in L$.
       Construa um AP que aceite $L$.

 \item (20 pontos) Construa uma gram\'{a}tica para cada uma das linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n \,|\, m>n\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^p{\tt d}^q \,|\, m>q \mbox{ ou } n<p\}$.
%        \item $\{ww^Rw \,\,\,|\,\,\, w\in \{a,b\}^*\}$
       \end{list}
       
 \item (10 pontos) Seja $G$ a gram\'{a}tica
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\rightarrow\, {\tt a}S \,|\, S{\tt b}
                  \,|\, {\tt ab} \,|\, SS$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^{e} uma express\~{a}o regular para $L(G)$.
        \item Construa duas deriva\c{c}\~{o}es mais a esquerda de {\tt aabb}.
        \item Construa as \'{a}rvores de deriva\c{c}\~{a}o para as deriva\c{c}\~{o}es da parte (b).
        \item Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item (10 pontos) Mostre que todos os s\'{\i}mbolos da gram\'{a}tica
       abaixo s\~{a}o \'{u}teis. Construa uma gram\'{a}tica $G_C$, sem regras de cadeia,
       equivalente \`{a} mesma. Mostre que $G_C$ cont\'{e}m s\'{\i}mbolos in\'{u}teis.
       \begin{enumerate}
        \item[\ ] \hspace*{1cm}$S \,\rightarrow\, A \,|\, CB$
        \item[\ ] \hspace*{1cm}$A \,\rightarrow\, C \,|\, D$
        \item[\ ] \hspace*{1cm}$B \,\rightarrow\, {\tt b}B \,|\, {\tt b}$
        \item[\ ] \hspace*{1cm}$C \,\rightarrow\, {\tt c}C \,|\, {\tt c}$
        \item[\ ] \hspace*{1cm}$D \,\rightarrow\, {\tt d}D \,|\, {\tt d}$
       \end{enumerate}

 \item (10 pontos) Prove que toda linguagem recursivamente enumer\'{a}vel
       \'{e} aceita por uma MT com um \'{u}nico estado final.

\end{enumerate}

\end{document}
\endinput
\end

