%Setup File
\input{setup.tex}


\begin{document}

\Cabecalho{Trabalho Prático 02 (TP02) - Algoritmo CYK}


\instrucoes{08/05/2014 até 23:55}

\section{Descrição}

Seja $G = (V, \Sigma, R, S)$ uma gramática livre do contexto (GLC) em que $V$ é o conjunto de variáveis,
$\Sigma $ o alfabeto, $R$ o conjunto de regras e $S$ o símbolo de partida.

O objetivo deste trabalho prático é a implementação do algoritmo CYK, de ordem polinomial, capaz de reconhecer
palavras geradas por uma GLC na forma normal de Chomsky (FNC). O nome desse algoritmo, que data de 1965, tem as iniciais
de seus criadores \emph{J. Cocke}, \emph{D. H. Younger} e \emph{T. Kasami}.

O algoritmo CYK, a partir de uma GLC $G$ na FNC e uma palavra $w$, realiza uma análise ascendente. Ele inicia com
a palavra $w$, que se deseja avaliar, e a cada passo tenta deduzir qual regra da gramática leva à geração da
palavra no passo seguinte, obtendo, ao final, uma matriz triangular ($M$). Caso o símbolo de partida da gramática
esteja na célula no topo da matriz, a palavra pertence à linguagem gerada pela gramática, caso contrário, ela não
pertence.

O algoritmo possui variadas aplicações práticas, tais como em  \emph{análise sintática}, em
\emph{bioinformática}, na verificação de \emph{alinhamento de sequências},
em \emph{linguística}, na verificação de estruturas de sentenças e palavras em \emph{linguagem natural}, entre outras.

O pseudo-código do algoritmo, que pode ser usado como base para implementação, é apresentado no Algoritmo
\ref{alg:primaleFRP}. Contudo, este trabalho também compreende um pequeno esforço da parte do aluno em pesquisar a
respeito do método em outras referências ou na Web. Algumas referências sugeridas:

\begin{itemize}
  \item Hopcroft, J.E., Motwani, R., Ullman, J.D. \emph{Introduction to Automata Theory, Languages and Computation}, 2nd ed., Addison-Wesley, 2001 (Seção 7.4.4, páginas 298 - 302);
  \item Menezes, P.B. \emph{Linguagens Formais e Autômatos}, 2a ed., Sagra Luzzatto, 2000 (Seção 3.9.2, páginas 122 - 124);
  \item Wikipedia: \url{http://en.wikipedia.org/wiki/CYK_algorithm}.
\end{itemize}

%referencias:
% http://en.wikipedia.org/wiki/CYK_algorithm
% http://www.di.ubi.pt/~desousa/2011-2012/TComp/algoCYK.pdf
% http://www.cs.toronto.edu/~frank/Useful/algorithm2e.pdf
% http://get-software.net/macros/latex/contrib/algorithm2e/doc/algorithm2e.pdf

\begin{algorithm}[h]
  \caption{Algoritmo CYK.} \label{alg:primaleFRP}
  \DontPrintSemicolon
  \SetKwInOut{Input}{input}
  \SetKwInOut{Output}{output}

  %\Input{$G = (V, \Sigma, R[1..r], P)$; palavra  $w$; Vetor<Booleano>}
  \Input{GLC $G$, palavra $w[1...n]$
  }
  \Output{\texttt{SIM}, se $w \in L(G)$ ou \texttt{NAO}, se $w \not\in L(G)$}

  \BlankLine

  Crie uma matriz booleana $T[n, n, | V |]$ com todas as células em \emph{Falso};

  \BlankLine

  \For{i = 1 TO n } {
    \For{each $V_{j} \rightarrow a_{i} \in R$} {
      $T[i, 1, j] \leftarrow Verdadeiro$;
    }
  }

  \BlankLine

  \For{i = 2 TO n} {
    \For{j = 1 TO n-i+1} {
      \For{k = 1 TO i-1} {
        \For{each $V_{A} \rightarrow V_{B}V_{C} \in R$} {
          \If{$T[j,k,B] \wedge T[j+k,i-k,C]$}{$T[j,i,A] \leftarrow Verdadeiro$;}
        }
      }
    }
  }

  \BlankLine

  \For{each $x \in S$} {
    \If{$T[1,n,x]$}{Retorne SIM;}
  }

  \BlankLine

  Retorne NAO;
\end{algorithm}


\subsection{Ideia principal}
\label{sec:Ideia}

Em termos informais, este algoritmo considera todas as subpalavras de $w$ e define $T[i, j, k]$ para ser \emph{verdadeiro} se a subpalavra a partir de $i$ de comprimento $j$ pode ser gerada a partir da variável $V_{k}$. Uma vez consideradas subpalavras de comprimento 1, ele passa para subpalavras de comprimento 2, e assim por diante. Para subpalavras de comprimento maior que 1, ele considera todas as possíveis partições da subpalavra em duas partes, e verifica se há alguma produção $A  \rightarrow BC \in R$ tal que $B$ corresponde à primeira parte e $C$ corresponde à segunda parte. Se assim for, ele registra $A$ como combinando toda a subpalavra. Quando esse processo for concluído, $w$ é gerada pela gramática se o símbolo de partida foi registrado para a palavra inteira.

A matriz booleana $T$ é uma representação da matriz triangular $M$, que é preenchida de baixo para cima com símbolos variáveis. Como exemplo, seja a gramática definida por: $G = \{\{S,A\}, \{a,b\}, R, S\}$, com $R = \{S \rightarrow AA$, $S \rightarrow AS$, $S \rightarrow b$, $A \rightarrow AS$, $A \rightarrow SA$, $A \rightarrow a\}$. Deve-se verificar se $G$ gera a palavra $abaab$.

A Figura \ref{fig:ex1}(A) apresenta o conteúdo da matriz após o primeiro passo do algoritmo. Ao término do primeiro passo, a linha inferior da matriz é preenchida com todas as variáveis que geram cada símbolo da palavra. Na Figura \ref{fig:ex1}, a palavra a ser verificada é apresentada logo abaixo da matriz $M$.

Nos passos seguintes, para preencher as linhas superiores, uma variável $A$ será colocada na matriz $M$ se existem duas outras variáveis $B$ e $C$ em que:

\begin{itemize}
  \item $A \rightarrow BC$ é uma regra;
  \item $B$ está à esquerda de $C$ e ambos estão ``por baixo'' e à direita de $A$.
\end{itemize}

As Figuras \ref{fig:ex1}(B) e \ref{fig:ex1}(C), apresentam o segundo e o quinto (e último) passos do algoritmo, respectivamente. Podemos concluir que $G$ gera a palavra $abaab$, já que o símbolo de partida $S$ encontra-se no topo da matriz $M$.

\begin{figure}[h]
   \centering
   \includegraphics[scale=0.5]{Exemplo1}
   \caption{Matriz $M$ construída a partir do primeiro, segundo e quinto (e último) passos do algoritmo CYK.}\label{fig:ex1}
\end{figure}


\section{Representação}

Para simplificar um pouco o formato dos dados de entrada consideramos que: o conjunto de terminais consiste das
letras minúsculas do nosso alfabeto, ou seja,  $\Sigma = \{a, b, \ldots, z \}$; o conjunto de variáveis
consiste das letras maiúsculas do nosso alfabeto, ou seja,  $ V = \{A, B, \ldots, Z \}$; e o símbolo $S$
é o símbolo de partida da gramática.


%\newpage

\subsection{Entrada}

Dadas as convenções anteriores, a entrada do programa será constituída de:

\begin{itemize}
  \item Uma linha contendo a palavra de entrada. Ela deve ter no máximo 50 símbolos.
  \item Uma linha contendo um inteiro positivo, $r$, que representa o número de regras da gramática.
  \item $r$ linhas contendo as regras da gramática. Cada regra deve ter o formato
  \texttt{X -> a$_1$ a$_2$ $\ldots$ a$_n$}, em que $\texttt{X}\in V$ e \texttt{a$_i$} $\in (V \cup \Sigma )$,
  com cada \texttt{a$_i$} separado de \texttt{a$_{i+1}$} por um único espaço.
\end{itemize}


\subsection{Saída}

O programa deve retornar apenas o resultado da aplicação do algoritmo dizendo:

\begin{itemize}
  \item \texttt{SIM}, se a gramática gera a palavra.
  \item \texttt{NAO}, se a gramática não gera a palavra.
\end{itemize}


\subsection{Exemplos de Entrada e Saída}

%Exemplo utilizado na Seção \ref{sec:Ideia}:

\EntradaSaida{
abaab \newline
6 \newline
S -> A A \newline
S -> A S \newline
S -> b \newline
A -> A S \newline
A -> S A \newline
A -> a
}{
SIM
}

%Exemplo em que a palavra pertence à linguagem gerada pela gramática:

\EntradaSaida{
abbabba \newline
7 \newline
S -> S F \newline
S -> a \newline
A -> C C \newline
A -> S S \newline
A -> C S \newline
C -> b \newline
F -> A S
}{
SIM
}

%Exemplo em que a palavra não pertence à linguagem gerada pela gramática:

\EntradaSaida{
aaabbabaaaabba \newline
8 \newline
S -> S F \newline
S -> a \newline
A -> C G \newline
A -> S S \newline
A -> C S \newline
C -> b \newline
F -> A S \newline
G -> C A
}{
NAO
}


\end{document}
