\documentclass[11pt,a4paper]{article}

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

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


\newcounter{conta}
%\newcounter{conta2}

\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 {\bf Trabalho de Recuperação} \hfill Entrega: até 5/11/2013

\vspace*{5mm}
\noindent\ \hrulefill \       

\vspace*{2mm} 
\noindent {\bf Observações:}
\begin{itemize}
 \item {\bf O trabalho é individual.}

 \item A nota do trabalho terá peso 2 e a da primeira prova peso 1 no cálculo da nota final da primeira prova.

 \item Escolha 7 dentre as 8 questões formuladas. O objetivo deste trabalho é verificar o nível de entendimento de parte
       do capítulo 2. Assim como existem questões simples (algumas um pouco trabalhosas, é verdade\ldots) relativos a
			 alguns conceitos e métodos (questões 1 a 6), existem aquelas que exigem um pouco mais de destreza (questões 7 e 8). 

 \item A interpretação de cada questão faz parte do trabalho. Caso alguma questão esteja ambígua ou incorreta,
       ou caso falte(m) elemento(s) importante(s) para o seu entendimento, faça as suposições e/ou correções que
			 achar convenientes {\bf e explicite-as}.

 \item Na correção de cada questão será analisado se a mesma foi respondida com {\bf rigor}, {\bf clareza} e
       {\bf objetividade}. O aluno perderá pontos significativos nas seguintes situações, por exemplo,
			 {\it mesmo se sua resposta estiver correta\/}:
       \begin{itemize}
        \item usa frases incoerentes, ou sem sentido, ou incorretas, ou que nada tenham a ver com o que foi perguntado;
        \item apresenta uma solução sem apresentar a(s) idéia(s) subjacente(s), dificultando a correção;
        \item apresenta uma solução conceitualmente deselegante;
        \item é prolixo, escrevendo coisas desnecessárias ao entendimento da solução.
       \end{itemize}
%       Dependendo do ``grau'' de tais impropriedades, o aluno pode até perder todos os pontos relativos à questão.

 \item Devolução: até as 9:30 horas do dia 5/11/2013, na sala 4023, ou em meu escaninho na Recepção do DCC, ou via
       {\it email\/}, ou em sala de aula.
\end{itemize}

\vspace*{2mm}
\noindent\ \hrulefill \       

\vspace*{3mm}

\begin{enumerate}
\item Obtenha um AFD que reconhe\c{c}a a linguagem $(a+b+c)^*a(a+b)(a+b+c)$.

\item Construa:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item um AFD, e
        \item uma express\~ao regular
       \end{list}
       para a linguagem $$\{w\in \{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ cont\'em número ímpar de {\tt a}s
       e não contém a subpalavra {\tt abc}}\}\mbox{.}$$ No item (a), apenas desenhe o diagrama de estados.
       No item (b), n\~ao será aceita expressão regular com sintaxe incorreta.

 \item Apresente um diagrama de estados para um AFN que reconhe\c{c}a a linguagem
       $$L=\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, {\tt 000} \mbox{ não é sufixo de } w\}$$ e que tenha as
       seguintes características:
       \begin{itemize}
        \item tem um único estado final; e
        \item para cada $w\in L$ existe uma única computação de sucesso.
       \end{itemize}

 \item Sejam as linguagens:
       \begin{itemize}
        \item $L_1$ denotada por $(00+11)^*(01+10)^*$, e
        \item $L_2$ denotada por $(00+001)^*$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa autômatos finitos $M_1$ e $M_2$ que reconheçam $L_1$ e $L_2$.
				\item Usando transições $\lambda$, construa, a partir de $M_1$ e $M_2$, um AFN$\lambda$ $M_3$ que
				      reconheça $L_1L_2$.
        \item Obtenha um AFN $M_4$ equivalente a $M_3$.
        \item Obtenha um AFD $M_5$ equivalente a $M_4$.
       \end{list}
       Use os métodos de transformação apresentados em aula.
 \item Mostre que $L-X$ é regular ou que não é, ou que pode ser regular e pode não ser, se:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L$ não é regular e $X$ é finita.
        \item $L$ não é regular e $X$ é regular.
        \item $L$ é regular e $X$ é regular.
        \item $L$ é regular e $X$ não é regular.
       \end{list}

 \item Prove que a linguagem $\{{\tt 1}x1^n\;|\; x \in \{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|>n\}$
       não é regular usando o lema do bombeamento.

 \item Seja a linguagem:
       \[L=\{a^ib^jc^k\;|\;i\not=j \;\mbox{\em ou}\; j\not=k\}\mbox{.}\]
       Suponha que na aplicação do lema do bombeamento para provar que $L$ não é regular, seja escolhida
			 $z=a^kb^{k!+k}c^{k!+k}$, em que $k$ é a constante do lema. Descubra a razão ``misteriosa'' para tal escolha.

 \item Mostre que as linguagens regulares são fechadas sob a operação {\em metade\/}:
       \[\mbox{\em metade\/}(L)=\{x\;|\; xy\in L \;\mbox{\em e}\; |x|=|y|\}\mbox{.}\]

\end{enumerate}

\end{document}
