\documentclass[12pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\usepackage{latexsym}

%=================================================================
%\addtolength{\topmargin}{1cm}
%\addtolength{\textheight}{1cm}
%=================================================================

\newcounter{conta}
\pagestyle{empty}
\hyphenation{pro-ble-mas re-gu-lar re-gu-la-res}
\begin{document}
 
\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 2002 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova/Especial} \hfill 07/11/2003

\begin{enumerate}

 \item Sejam $L_1$ e $L_2$ liguagens sobre $\{{\tt 0},{\tt 1}\}$. Encontre
       exemplos de linguagens $L_1$ e $L_2$ tais que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(L_1\cup L_2)^*\not=L_1^*\cup L_2^*$.
        \item $L_1\not\subseteq L_2$, $L_2\not\subseteq L_1$ e
              $(L_1\cup L_2)^*=L_1^*\cup L_2^*$.
       \end{list}

 \item Descreva mais formalmente (usando conjuntos finitos, uni\~ao,
       interse\c c\~ao, concatena\c c\~ao, fecho de Kleene, etc.) as
       linguagens a seguir, ambas sobre o alfabeto $\{0,1\}$. Fa\c ca
       tamb\'em uma gram\'atica para a primeira.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de, no m\'{\i}nimo, 3 s\'{\i}mbolos,
              cujo segundo s\'{\i}mbolo \'e diferente do \'ultimo.
        \item O conjunto n\~ao vazio das palavras de tamanho 2 a 100.
       \end{list}

 \item Para cada linguagem abaixo fa\c ca um aut\^omato finito
       determin\'{\i}stico que a reconhe\c ca.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 00}\}^*\{{\tt 11}\}^*\{{\tt 0}\}^*$
        \item $(\{{\tt 0},{\tt 1}\}^*\{{\tt 01}\}\{{\tt 0},{\tt 1}\}^*)
                \cap\{{\tt 00},{\tt 01},{\tt 10},{\tt 11}\}^*$.
       \end{list}

 \item Seja um AFN $M=(E,\Sigma,\delta,I,F)$. Como obter um AFN $M'$ equivalente tal que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $M'$ tem um \'unico estado inicial?
        \item $M'$ tem um \'unico estado final?
       \end{list}

 \item Mostre que a linguagem $\{x{\tt 1}y\,|\,x,y\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|=|y|\}$
       n\~ao \'e regular.

 \item Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item se $L_1$ e $L_2$ n\~ao s\~ao linguagens regulares, ent\~ao
              $L_1\cap L_2$ n\~ao \'e linguagem regular.
        \item se  $L_1\cap L_2$ n\~ao \'e linguagem regular, ent\~ao $L_1$ n\~ao \'e
              linguagem regular ou $L_2$ n\~ao \'e linguagem regular .
        \item se $L_1,L_2,L_3,\ldots$ s\~ao linguagens regulares, ent\~ao
              $\cup_{n=1}^\infty$ \'e linguagem regular.
       \end{list}

\end{enumerate}

\end{document}
\begin{enumerate}
