\documentclass[11pt, a4paper]{article}

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

\newcounter{conta}


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

\begin{document}

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

\section{Linguagens Formais}

\begin{enumerate}

 \item $\lambda$ pode ser símbolo de um alfabeto?
 
       Resp: não. ($\lambda$ é palavra; nenhuma palavra pode ser usada como símbolo.)

 \item Como expressar a palavra com mil 0s usando o alfabeto $\{0\}$?
 
       Resp: $0^{1000}$.

 \item Quantas palavras tem a linguagem $\{\}$ de alfabeto $\{a,b\}$?
 
       Resp: 0. (conjunto vazio não tem membro.)

 \item Quantas palavras tem a linguagem $\{\lambda\}$ de alfabeto $\{a,b\}$?
 
       Resp: 1. (A palavra vazia tem 0 símbolos, mas a linguagem tem uma palavra: a palavra vazia.)

 \item Quantas palavras tem $\{w\in\Sigma^*\,|\,\ 0\leq |w|\leq 4\}$?
 
       Resp: $2^0+2^1+2^2+2^3+2^4=1+2+4+8+16=31$.

 \item Se $\Sigma$ é um alfabeto, o conjunto potência de $\Sigma^*$ \'e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto de todas as palavras no alfabeto $\Sigma$.
        \item O conjunto de todas as linguagens de alfabeto $\Sigma$.
        \item Não é conjunto.
       \end{list}

       Resp: (c). (Todo subconjunto de $\Sigma^*$ é linguagem e vice-versa.)

 \item Se todos os $n$ símbolos de uma palavra são diferentes, quantas subpalavras ela tem?
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $n$
        \item $n+1$
        \item $1+C(n+1,2)$
        \item $1+2+\ldots+n$
       \end{list}

       Resp: (c). (a opção (d) deixa a subpalavra $\lambda$ de fora.)

 \item Se $L$ é uma linguagem, então $LLL$ é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item toda palavra $xxx$ em que $x\in L$.
        \item toda palavra $xyz$ em que $x,y,z\in L$.
        \item igual a $L$.
        \item nem (a), nem (b), nem (c).
       \end{list}

       Resp: (b). (Os três pedaços, x, y e z, podem ser idênticos, mas podem ser diferentes.)

 \item Seja $L=\{a^nb^n\,|\, n\geq 0\}^3$. Marque \underline{todas} as afirmativas corretas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\lambda\in L$
        \item $abab\in L$
        \item $ababab\in L$
        \item $abaabbaaabbb\in L$
       \end{list}

       Resp: (a), (b), (c) e (d). (Todas estão corretas.)

 \item Qual linguagem abaixo difere das outras?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{0\}^*$
        \item $\{\lambda,0\}^*$
        \item $\{0\}^+$
        \item $\{\lambda,0\}^+$
       \end{list}

       Resp: (c) (Apenas as outras contêm $\lambda$.)

 \item Para cada linguagem, diga se ela tem (1) apenas palavras com número par de símbolos, (2) apenas palavras com
       número ímpar de símbolos ou (3) tem palavras com número par e com número ímpar de símbolos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\lambda,0,1\}$
        \item $\{\}^*$
        \item $(\{0,1\}\{0,1\})^*$
        \item $\{00,11\}^*\{0,1\}$
       \end{list}

       Resp: (a) 3; (b) 1; (c) 1; (d) 2. 

 \item Para que linguagens $L$, $L^*=\{\lambda\}$?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Nenhuma.
        \item Apenas $\{\}$.
        \item Apenas $\{\lambda\}$
        \item $\{\}$ e $\{\lambda\}$
       \end{list}

       Resp: (d) (Segue da definição de fecho de Kleene.)

 \item Que afirmativa está incorreta?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $LL^*=L^+$
        \item $L^*L^+=L^+$
        \item $L^*=L^+\cup\{\lambda\}$
        \item $L^+=L^*-\{\lambda\}$
       \end{list}

       Resp: (d). (se $\lambda\in L$, então $L^+\not=L^*-\{\lambda\}$.)
\end{enumerate}

\end{document}

\end{frame}
