\documentclass[11pt,a4paper]{article}

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

\usepackage{verbatim}
\usepackage{gastex}
\usepackage[usenames]{color}


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

\begin{document}
 
\vspace*{15mm}
\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 Segunda Prova} \hfill 20/10/2011

\vspace*{5mm}
\begin{enumerate}
 \item Apresente expressões regulares para as seguintes linguagens, a partir de autômatos finitos
       determinísticos mínimos para as mesmas:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ $w$ não contém {\tt 0}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ $w$ não contém {\tt 01}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ $w$ não contém {\tt 010}}\}$.
       \end{list}
 
 \item Apresente gramáticas livres do contexto que gerem:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^n{\tt b}^{2n}{\tt c}^k\,|\, n,k\geq 0\}$.
        \item $\{{\tt a}^n{\tt b}^k{\tt a}^n\,|\, n,k\geq 1\}$.
        \item $\{{\tt a},{\tt b}\}^*-\{w\in\{{\tt a},{\tt b}\}^*\,|\, w=w^R\}$.
       \end{list}

 \item Seja a gramática $G$:
       \begin{quote}
        $A \,\rightarrow\, {\tt a}A{\tt bb} \,|\, B$ \\
        $B \,\rightarrow\, {\tt b}B{\tt aa} \,|\, A \,|\, \lambda$
       \end{quote}
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma gramática livre do contexto equivalente a $G$ sem regras $\lambda$ nem unitárias.
        \item Mostre que $G$ é ambígua.
        \item Obtenha um autômato de pilha que reconheça $L(G)$.
       \end{list}

 \item Para cada linguagem a seguir, dizer se ela é (1) regular, (2) livre do contexto, mas não regular, ou
       (3) não livre do contexto. Justifique.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{{\tt a}}(w)=n_{{\tt b}}(w)=n_{{\tt c}}(w)\}$. \\
              ($n_{s}(w)$ é o número de símbolos $s$ na palavra $w$.)
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ representa uma potência de 2 em binário}\}$.
        \item $\{{\tt a}^n{\tt b}^k\,|\, n\not=k\}$.
       \end{list}
\end{enumerate}

\end{document}
