\documentclass[12pt, a4paper]{article}

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

\newcounter{conta}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segundo Trabalho Prático} -- Turmas D e W\hfill {Entrega: dia 6/12/2012 até as 23:55h}

\vspace*{7mm}
\section{Enunciado}
\noindent Faça um programa interativo de \emph{auxílio à construção de gramáticas livres do contexto}, que use uma notação tipo BNF, com as seguintes funcionalidades:
\begin{list}{(\alph{conta})}{\usecounter{conta}}
 \item definir variável de partida;
 \item inserir regra;
 \item remover regra;
 \item remover variável (para isto, basta remover todas as regras em que ela aparece);
 \item listar variáveis inúteis.
\end{list}
Uma variável é uma cadeia de caracteres entre $<$ e $>$. E um terminal é uma cadeia de caracteres entre aspas; se a cadeia de caracteres entre aspas não contiver brancos, nem for $<$ ou $>$, o terminal pode ser escrito simplesmente entre brancos (não há necessidade das aspas).

O usuário deverá poder construir uma GLC $G=(V,\Sigma,R,P)$ de forma incremental, usando as funcionalidades (a) a (e) na ordem em que desejar.

Durante a construção de $G$, um pedido para listar as variáveis inúteis de $G$, pedido (e), é atendido em dois passos:
\begin{list}{(\alph{conta})}{\usecounter{conta}}
 \item determine o conjunto $V'=\{X\in V\,|\, X\stackrel{*}{\Rightarrow} w \mbox{ para algum }w\in\Sigma^*\}$ assim:

       \begin{tabbing} \footnotesize
        xxx\=xxx\=xxx\=xxx \kill \\
        \>Entrada: uma GLC $G=(V,\Sigma,R,P)$. \\
        \>Saída: $V'=\{X\in V\,|\, X\stackrel{*}{\Rightarrow} w \mbox{ para algum } w\in\Sigma^*\}$. \\
        \>$V'\leftarrow \emptyset$;  \\
        \>{\bf repita} \\
        \> \> $N\leftarrow \{X\in V\,|\, X\not\in V', X\rightarrow z\in R \mbox{ e } z\in(V'\cup\Sigma)^*\}$; \\
        \> \> $V'\leftarrow V'\cup N$ \\
        \> {\bf até} $N=\emptyset$; \\
        \> retorne $V'$.
       \end{tabbing}

\pagebreak
 \item determine o conjunto $V''=\{X\in V'\,|\, P\stackrel{*}{\Rightarrow} uXv \mbox{ para algum }
       u,v\in(V'\cup\Sigma)^*\}$ assim:

       \begin{tabbing} \footnotesize
        xxx\=xxx\=xxx\=xxx \kill \\
         \>Entradas: uma GLC $G=(V,\Sigma,R,P)$ e $V'$. \\
         \>Saída: $V''=\{X\in V'\,|\, P\stackrel{*}{\Rightarrow} uXv \mbox{ para algum } u,v\in(V'\cup\Sigma)^*\}$. \\
         \>$V''\leftarrow \emptyset$; $N\leftarrow \{P\}$; \\
         \>{\bf repita} \\
         \> \> $V''\leftarrow V''\cup N$; \\
         \> \> $N\leftarrow \{Y\in V'\,|\, Y\not\in V'' \mbox{ e } X\rightarrow uYv \mbox{ para algum } X\in N
                \mbox{ e } u,v\in(V'\cup\Sigma)^*\}$ \\
         \>{\bf até} $N=\emptyset$; \\
         \>retorne $V''$.
       \end{tabbing}
\end{list}
As variáveis inúteis são aquelas em $V-V''$. Caso o usuário peça para eliminar uma dessas variáveis inúteis, via a funcionalidade (d), basta remover todas as regras em que ela aparece.


\section{Informações adicionais}

\begin{enumerate}
 \item O trabalho é individual.
 \item Deve ser usada uma das linguagens: C, C++ ou Java.
 \item A apresentação do monitor sobre o trabalho será feita na segunda aula do dia 08/11. Nessa aula serão abordados
       aspectos importantes sobre como o programa deve ser confeccionado e sobre a apresentação do aluno (com execução
       do programa e entrevista) a ser feita no dia 7/12/2012.
 \item O código fonte deverá ser entregue, via Moodle, até o dia 6/12/2012 às 23:55h.
 \item O trabalho deverá ser apresentado no dia 7/12/2012 de 8 às 9:30h (turma W) e de 9:30 às 12:00h (turma D).
\end{enumerate}

\end{document}
