\documentclass[12pt,a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Prova Suplementar}. Valor: 34 pontos. \hfill 3/12/2013

\vspace*{3mm}
\begin{enumerate}

 \item (12 pontos) Determine uma expressão regular que denote o complemento de $\{{\tt 01}\}^*$ da seguinte
       forma:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Desenhe o diagrama de estados de um autômato finito determinístico de 3 estados que reconheça
				      $\{{\tt 01}\}^*$.
				\item A partir desse autômato, obtenha um outro que reconheça o complemento de  $\{{\tt 01}\}^*$.
				\item A partir desse último, explicite um diagrama de expressões regulares (diagrama ER) a ser usado como
				      ponto de partida para a obtenção de uma expressão regular.
				\item Obtenha a expressão regular, a partir do diagrama ER, por meio do método de eliminações sucessivas de
				      estados.
			 \end{list}

 \item (8 pontos) Diga se é verdade ou falso, \underline{justificando}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Se $L_1$ e $L_2$ são linguagens livres do contexto e $L_1\subseteq L_2$, então $L_2-L_1$ é uma linguagem
				      livre do contexto.
				\item Uma gramática $(V,\Sigma,R,P)$ em que cada regra é da forma $X\rightarrow w$, sendo $X\in V$,
				      $w\in (V\cup\Sigma)^*$ e $|w|\leq 2$, pode gerar qualquer linguagem livre do contexto.
			 \end{list}

 \item (6 pontos) Mostre que são equivalentes os seguintes critérios de aceitação para máquinas de Turing:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Por estado final: uma palavra $w$ é aceita se e somente se a máquina atinge algum estado final
				      ao processar $w$,.
				\item Por parada: uma palavra $w$ é aceita se e somente se a máquina para ao processar $w$.
			 \end{list}

 \item (8 pontos) Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma GLC $G$, determinar se $L(G)\cap \{1\}^*\not=\emptyset$.
        \item Dada uma MT, determinar se todos os seus estados são úteis. Estado útil: aquele que é atingido
				      durante o processamento de alguma palavra de entrada.
       \end{list}

\end{enumerate}

\end{document}
