\documentclass[11pt]{article}
 
\newcounter{conta}
\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{fullpage}
\pagestyle{empty}

\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 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Exame Especial} \hfill 12/07/2010

\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 sobre $\{a,b,c\}$ que n\~{a}o cont\^{e}m
              $aa$.
        \item O conjunto das palavras sobre $\{a,b\}$ nos quais cada $a$
              \'{e} precedido (imediatamente) ou seguido (imediatamente) por $b$.
        \item O conjunto das palavras de tamanho \'{\i}mpar sobre $\{a,b\}$
              que cont\^{e}m exatamente dois $b$'s.
       \end{list}

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

 \item (10 pontos) Seja $L$ a linguagem $\{w\in\{a,b\}^*\,\,\,|\,\,\, 
       w$ tem prefixo contendo mais $b$'s que $a$'s$\}$. Por exemplo,
       $baa, abba, abbaaa\in L$, mas $aab, 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 $\{a^mb^n \,\,\,|\,\,\, m>n\}$.
%        \item $\{a^mb^nc^pd^q \,\,\,|\,\,\, m+n \geq p+q\}$.
        \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\,\,\, aS \,\,\,|\,\,\, Sb
                  \,\,\,|\,\,\, 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 $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 (15 pontos) Mostre que 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\,\,\, bB \,\,\,|\,\,\, b$
        \item[\ ] \hspace*{1cm}$C \,\,\,\rightarrow\,\,\, cC \,\,\,|\,\,\, c$
        \item[\ ] \hspace*{1cm}$D \,\,\,\rightarrow\,\,\, dD \,\,\,|\,\,\, d$
       \end{enumerate}

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

\end{enumerate}

\end{document}
\endinput
\end

