\documentclass[11pt, a4paper]{article}

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

\newcounter{conta}


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

\begin{document}

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

\section{Gramáticas}

\begin{enumerate}

 \item O conjunto de variáveis de uma gramática não pode ser vazio. Certo ou errado?
 
       Resp: Certo. (Deve conter a variável de partida.)

 \item O conjunto de regras de uma gramática não pode ser vazio. Certo ou errado?
 
       Resp: Errado. (Sem regras uma gramática gera $\{\}$.)

 \item Regra recursiva a esquerda serve para gerar palavras da esquerda para a direita. Certo ou errado?
 
       Resp: Errado. (Serve para gerar palavras da direita para a esquerda.)

 \item Se uma variável aparece em uma única regra ela é inútil. Certo ou errado?
 
       Resp: Errado. (Se for a variável de partida, ela é útil.)

 \item Se um terminal aparece em uma única regra ele é inútil. Certo ou errado?
 
       Resp: Errado. (Uma única aparição pode ser suficiente para prever todas as suas ocorrências.)

 \item Um esquema de derivação é uma derivação de certa palavra. Certo ou errado?

       Resp: Errado. (Um esquema de derivação não é derivação. Instâncias do esquema são derivações.)

 \item Seja $G$ a gramática de regras:
       \begin{quote}
        $P\,\rightarrow\, 0 B 1\,|\, \lambda$
       \end{quote}
       Em quantos passos é derivada uma palavra $0^n1^n$?

       Resp: $n+1$. ($P\,\stackrel{n}{\Rightarrow}\,0^nP1^n\,\Rightarrow\, 0^n1^n$.)

 \item Seja $G$ a gramática de regras:
       \begin{quote}
        $A\,\rightarrow\, 0 B \,|\, \lambda$ \\
        $B\,\rightarrow\, A 1$
       \end{quote}
       $L(G)$ é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\lambda\}$.
        \item $\{0\}^*\{1\}$.
        \item $\{0\}^*\{1\}^*$.
        \item $\{0^n1^n\ \,|\, n\geq 0\}$.
       \end{list}

       Resp: (d). (Para $n\geq 0$: $A\,\stackrel{2n}{\Rightarrow}\,0^nA1^n\,\Rightarrow\, 0^n1^n$.)

 \item Seja $G$ a gramática de regras:
       \begin{quote}
        $P\,\rightarrow\, 0 B 1\,|\, \lambda$ \\
        $01\,\rightarrow\,10$
       \end{quote}
       Que afirmativa está correta?

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(G)=\{0^n1^n\,|\,n\geq 0\}$.
        \item $L(G)=\{0,1\}^*$.
        \item $G$ não é gramática aceitável.
        \item Existe $w\in\{0,1\}^*$ tal que $w\not\in L(G)$.
       \end{list}

       Resp: (b). (As duas primeiras regras geram $L(G)=\{0^n1^n\,|\,n\geq 0\}$. A terceira permuta 0s e 1s.)

 \item Seja $G$ a gramática de regras:
       \begin{quote}
        $E\,\rightarrow\, E+T\,|\, T$ \\
        $T\,\rightarrow\, N \,|\, (E)$ \\
        $N\,\rightarrow\, DN \,|\, N$ \\
        $D\,\rightarrow\, 0 \,|\, 2\,|\, 4\,|\, 6\,|\, 8$
       \end{quote}
       Responda:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Para que $n$ $P\,\stackrel{n}{\Rightarrow}\,((0))$?
        \item $E\,\stackrel{*}{\Rightarrow}\,((2)+(2))$?
        \item $E\,\stackrel{*}{\Rightarrow}\,\lambda$?
        \item $G$ apresenta recursão à esquerda, à direita e no meio. Certo ou errado?
       \end{list}

       Resps:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $7$. ($E\,\Rightarrow\,T\,\Rightarrow\,(E)\,\Rightarrow\,(T)\,\Rightarrow\,((E))
                   \,\Rightarrow\,((T))\,\Rightarrow\,((N))\,\Rightarrow\,((0))$.)
        \item Sim. ($E\,\Rightarrow\,T\,\Rightarrow\,(E)\,\Rightarrow\,(E+T)\,\Rightarrow\,(T+T)
                   \,\Rightarrow\,((E)+T)\,\Rightarrow\,((T)+T)\,\Rightarrow\,((N)+T)\dots$.)
        \item Não. (Impossível gerar $\lambda$ a partir de $E$.)
        \item Certo. ($E$ é recursiva à esquerda e no meio (indireta). $N$ é recursiva à direita.)
       \end{list}

\end{enumerate}

\end{document}

\end{frame}
