\documentclass[11pt, a4paper]{article}

\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}

\newcounter{conta}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\begin{center}
QUESTIONÁRIO 3
\end{center}

\section{Autômatos Finitos Determinísticos}

\begin{enumerate}

 \item O determinismo segue do fato de que:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A função de transição é total.
        \item Existe um único estado inicial.
        \item Para cada par (estado, símbolo) há um único estado sucessor.
        \item Ambos, (b) e (c).
       \end{list}
 
       Resp: (d). ((b) e (c) são ambos necessários para o determinismo, mas não (a).)

 \item Todo AFD tem estado de erro (a partir do qual não se alcança estado final). Certo ou errado?
 
       Resp: Errado. (Se toda palavra é prefixo de uma palavra aceita, o AFD não tem estado de erro.)

 \item Todos os AFDs em que todos os estados são estados finais são equivalentes. Certo ou errado?
 
       Resp: Certo. (Reconhecem $\Sigma^*$.)

 \item Se um AFD não tem estados finais:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Não está de acordo com a definição.
        \item Reconhece tudo.
        \item Reconhece $\{\}$.
        \item Reconhece $\{\lambda\}$.
       \end{list}
 
       Resp: (c). (Se o conjunto de estados finais é vazio, nenhuma palavra é aceita.)

 \item Um AFD que contenha um ciclo em seu diagrama de estados:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Reconhece uma linguagem infinita.
        \item Entra em loop e nunca para.
        \item Não pode reconhecer $\{\}$.
        \item Pode reconhecer $\{\lambda\}$.
       \end{list}
       Marque a que está correta.
 
       Resp: (d). (Um AFD sempre para após consumir a palavra. Após um ciclo, nem sempre algum estado
       final é alcançável.)

 \item Se dois AFDs $M_1$ e $M_2$ não têm estados inúteis (aqueles não alcançáveis a partir dos respectivos
       estados iniciais), então o produto de $M_1$ e $M_2$ também não tem estados inúteis. Certo ou errado?
 
       Resp: Errado. (Exemplo: se o inicial $i_1$ de $M_1$ não participa de ciclo (não há transição chegando
             nele) e $e_2$ é um estado diferente do inicial de $M_2$, $[i_1,e_2]$ é inútil.)

 \item Se $i$ é o estado inicial de um AFD $M$ e $\hat{\delta}(i,x)=i$, então:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $xy\in L(M)$ para algum $y$.
        \item Se $\lambda\in L(M)$, então $x^n\in L(M)$ para todo $n\geq 0$.
        \item Se $y\in L(M)$, então $xy\in L(M)$.
        \item Se $xy\in L(M)$, então $y\in L(M)$.
       \end{list}
       Marque a incorreta.
 
       Resp: (a). (Se $L(M)=\{\}$, (a) está incorreta. Se $\lambda\in L(M)$, $i$ é estado final: segue-se (b).
       (c) e (d) seguem do fato de que o ciclo de $i$ a $i$ lendo-se $x$ pode ser percorrido 0 ou 1 vez antes
       da leitura de $y$.)

 \item Se $L$ é uma linguagem finita:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Pode não ser reconhecível por AFD.
        \item Existe AFD que reconhece $L$ em que todos os ciclos são laços envolvendo estados não finais.
        \item O número de estados necessários para um AFD mínimo que aceite $L$ pode ser astronômico...
        \item Pode não ser reconhecível por AFD com um único estado final.
       \end{list}
       Marque a incorreta.

       Resp: (a). (Para toda linguagem finita existe AFD. Em ``formato de árvore'', justifica (b). Um conjunto
       finito pode ter um número astronômico de palavras e, neste caso, tem-se (c). Notando-se que não existe AFD
       com menos de 2 estados que aceite $\lambda$ e $a$, tem-se (d).)

 \item Se $\{a^nb^n\,|\,n\geq 0\}\subseteq L$, então não existe AFD que aceite $L$. Certo ou errado?

       Resp: Errado. ($\{a^nb^n\,|\,n\geq 0\}\subseteq \{a,b\}^*$ e existe AFD para $\{a,b\}^*$.)
 
 \item Se $L$ é reconhecida por AFD, então um subconjunto de $L$ também é. Certo ou errado?

       Resp: Errado. (Existe AFD para $\{a,b\}^*$ e $\{a^nb^n\,|\,n\geq 0\}\subseteq \{a,b\}^*$.)
 
 \end{enumerate}

\end{document}

\end{frame}
