\documentclass[11pt,a4paper]{book}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{verbatim}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\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 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Segunda Prova} \hfill 21/10/2010

\vspace*{3mm}
\begin{flushleft}
Escolha 9 dos 10 ítens. Cada item vale 3 pontos.
\end{flushleft}

\begin{enumerate}
 \item Determine expressões regulares que denotem as linguagens sobre $\{{\tt 0},{\tt 1}\}$ a seguir:
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item O conjunto das palavras em que {\tt 0}s só podem ocorrer em posições pares (segunda, quarta etc.).
       \item O conjunto das palavras que não têm {\tt 011} como subpalavra.
      \end{list} 

 \item Para cada linguagem a seguir, construa um APD, se poss\'{\i}vel. Se n\~ao for poss\'{\i}vel,
       construa um APN. Crit\'erio de reconhecimento: por estado final {\bf e} pilha vazia.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 0\}\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 0\}$.
        \item $\{x\#yx^R\,|\, x\in \{{\tt 0},{\tt 1}\}^*, y\in\{\lambda,{\tt 1}\}\}$.
       \end{list}

 \item Para cada linguagem a seguir, construa uma GLC, se poss\'{\i}vel. Se n\~ao for poss\'{\i}vel,
       diga explicitamente que é impossível (sem provar).
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n\,|\,m>n\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^{2(m+n)}\,|\,m,n\geq 0\}$.
%        \item $\{{\tt a}^m{\tt b}^n{\tt c}^{2(m+n)}\,|\,m>n\}$.
       \end{list}

 \item Seja a GLC $G=(\{P,A,B,Q,R\},\{{\tt a},{\tt b}\},X,P)$ em que $X$ cont\'em as regras:
              \begin{quote}
               $P\,\rightarrow\, Q \,|\, R$ \\
               $Q \,\rightarrow\, {\tt a}Q{\tt a} \,|\, B$ \\
               $R \,\rightarrow\, {\tt b}R{\tt b} \,|\, A$ \\
               $A \,\rightarrow\, {\tt a}A{\tt a} \,|\, \lambda$ \\
               $B \,\rightarrow\, {\tt b}B{\tt b} \,|\, \lambda$
              \end{quote} 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ é ambígua.
        \item Usando m\'etodos vistos em aula ou do livro-texto, construa uma GLC $G'$, equivalente a $G$,
              sem regras $\lambda$ e sem regras unit\'arias.
       \end{list}

 \item Seja $L=\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\, m\not=n \mbox{ ou } n\not=k\}$. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L$ é livre do contexto.
        \item $\overline{L}$ não é livre do contexto.
       \end{list}
\end{enumerate}

\end{document}
