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

\vspace*{3mm}
\begin{enumerate}
 \item (20 pontos) Seja $\Sigma=\{{\tt 0},{\tt 1}\}$. D\^{e} express\~{o}es regulares que
       denotem os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in \Sigma^*\,|\, w \mbox{ n\~{a}o cont\'em {\tt 11}}\}$.
        \item $\{w\in \Sigma^*\,|\, w \mbox{ cont\'em {\tt 11} e $|w|$ \'e
              \'{\i}mpar}\}$.
       \end{list}

 \item (10 pontos) Fa\c{c}a um aut\^omato finito n\~ao determin\'{\i}stico
       \textit{ sem transi\c{c}\~oes $\lambda$} que reconhe\c{c}a
       a linguagem denotada pela express\~ao regular: $(0+1)^*2+(0+2)^*1+(1+2)^*0$.

 \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 $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o n\'umero de {\tt a}s em $w$
              \'e maior que o de {\tt b}s}\}$. Use o resultado anterior e
               propriedades de fecho.
       \end{list}

 \item (10 pontos) Construa um aut\^omato de pilha que reconhe\c{c}a
       $\{{\tt a}^m{\tt b}^n \,|\, m>n\}$.

 \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 $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o n\'umero de {\tt a}s em $w$
              \'e maior que o de {\tt b}s}\}$.
       \end{list}

 \item (10 pontos) Defina o que \'e gram\'atica amb\'{\i}gua e apresente
       uma gram\'atica amb\'{\i}gua e outra n\~ao amb\'{\i}gua para
       a linguagem $\{\lambda,{\tt 0}\}\{\lambda,{\tt 1}\}$.

 \item (10 pontos) Fa\c{c}a uma MT que reconhe\c{c}a $\{{\tt 00}\}^*$ por parada.

\end{enumerate}

\end{document}
\endinput
\end

