\documentclass[11pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
%\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage         {amsfonts}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2018 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Segunda Prova} \hfill 23/10/2018 \hfill Valor: 23 pontos

\vspace*{3mm}
\begin{enumerate}
 \item Prove que $\{{\tt 0}^nx{\tt 0}^n\,|\, x\in\{{\tt 1}\}^* \mbox{ e } n\in\mathbb{N}\}$ não é linguagem regular usando o teorema da invariância à direita ou o lema do bombeamento.
 \item Seja $L_1$ uma linguagem \emph{não livre do contexto}. Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item se $L_2$ é uma linguagem finita, $L_1-L_2$ não é livre do contexto;
        \item se $L_2$ é uma linguagem regular, $L_1-L_2$ pode ser regular.
       \end{list}
 \item Encontre expressões regulares que denotem os conjuntos:
         \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém {\tt aba}$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém exatamente um {\tt aba}$\}$.
         \end{list}
 \item Construa uma GLC que gere e um AP que reconheça $\{{\tt 0}^nx{\tt 0}^n\,|\, x\in\{{\tt 1}\}^* \mbox{ e } n\in\mathbb{N}\}$.
 \item Crie GLCs para:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^m{\tt b}^{2m+n}{\tt c}^{3n}\,|\,m,n\in\mathbb{N}\}$;
        \item $L_2=\{xy\in\{{\tt 0},{\tt 1}\}^*\,|\, |x|=|y| \mbox{ e } x\not=y^R\}$;
        \item $(L_1L_2)^+\cup (L_2L_1)^*$.
       \end{list}
 \item Seja a GLC:
      \begin{enumerate}
       \item[\ ] $X\,\rightarrow\, {\tt 0}X\,|\,{\tt 0}X{\tt 1}\,|\,\lambda$
      \end{enumerate}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Mostre que essa GLC é ambígua;
        \item encontre uma GLC não ambígua equivalente.
       \end{list}
 \item Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ]$S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1}$
        \item[\ ]$A \,\rightarrow\, {\tt 0}A{\tt 0} \,|\, \lambda$
       \end{enumerate}
       Obtenha GLCs equivalentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item na forma normal de Chomsky;
        \item na forma normal de Greibach.
       \end{list}
\end{enumerate}

\end{document}
