Problema E



Algoritmo CYK (de Cocke, Younger e Kasami)

Problema

O objectivo deste exercício é a implementação de um algoritmo polinomial de reconhecimento de palavras por uma gramática algébrica na sua forma normal de Chomsky. Este algoritmo foi desenvolvido independentemente por J. Cocke, D. H. Younger e T. Kasami, em 1965 e permite saber se uma palavra w pertence à linguagem gerada por uma gramática algébrica em forma normal de Chomsky G.

Este algoritmo pertence a família dos algoritmos dinâmicos (dinâmica de programação dinâmica) e tem uma complexidade de O(|w|3).

Este realiza uma análise da palavra de forma ascendente (bottom-up). O algoritmo começa com a palavra por analizar e tente deduzir que produção contrinbua directamente a geração desta utlima. O resultado é uma matriz triangular. Se o simbolo inicial esta na célula de topo da matriz então a palavra foi reconhecida, senão a palavra não pertence a linguagem gerada pela gramática em forma normal de Chomsky.

O algoritmo é descrito com todo o rigor e detalhe nos apontamentos das aulas teórica e existem inúmeras fontes de informação na web e na bibliografia indicada nas aulas. Pelo que este enunciado não apresenta o algoritmo mas sim dois exemplos elucidativos, um simples outro mais geral. O leitor é então fortemente aconselhado a consultar os apontamentos para ter os detalhes todos do algoritmo. Assim sendo:

Seja G={{S,A},{a,b},P,S} com P={ SAA, SAS, Sb, AAS, ASA, Aa}

Será que abaab pertence à linguagem gerada por G?

O algoritmo começa por inicializar uma matriz triangular M de base de tamanho |abaab|=5 que será preenchida de baixo parta cima com não-terminais:

 
  
   
    
     
abaab

A linha

abaab

vai servir de base a inicialização do processo de preenchimento da matriz. Esta inicialização consiste em preencher a ultima linha com os não terminais que geram os terminais situados imediatamente por baixo.

De reparar que cada célula da matriz contém um conjunto (lista) de não terminais.

Obtemos então a matriz seguinte:

 
  
   
    
ASAAS
abaab

Repare que se vários não terminais gerassem a então estes estariam todos nas células por cima das células contendo a.

O processo de preenchimento funciona da linha i=4 até a linha 1. Para preencher uma célula M[i,j] o algoritmo vai tentar utilizar os não terminais presentes nas linhas anteriores e nas colunas a direita (ou seja os não terminais presentes em M[k,l] com i<k≤ 5 e jl≤ 5).

Um não terminal N é colocado na matriz em M[i,j] a custa de dois outros não terminais P e Q se

Dada uma linha i, o processo vare a linha toda. Repare que este processo pode não poder preencher algumas células, estas ficando assim vazias.

Se repetimos este processo de baixo para cima até chegar ao topo da matriz então podemos determinar se a palavra analizada pertence a linguagem. Para tal basta ver se S está na célula M[1,1].

Vejamos o processo linha a linha:

 
  
   
A,SASA,S
ASAAS
abaab

M[4,4]={A,S} porque M[5,4]=A, M[5,5]=S, AAS e SAS são produções.

M[4,3]=S porque temos M[5,3]=A e M[5,4]=A e que SAA é produção.

M[4,2]=A porque M[5,2]=A, M[5,3]=A, AAA é produção.

M[4,1]={A,S} porque M[5,1]=A, M[5,2]=S, AAS e SAS são produções.

As linhas seguintes preenchem-se de forma similar.

 
  
A,SA,SA
A,SASA,S
ASAAS
abaab
 
A,SA,S
A,SA,SA
A,SASA,S
ASAAS
abaab
A,S
A,SA,S
A,SA,SA
A,SASA,S
ASAAS
abaab

Neste ponto ja podemos concluir: abaab pertence a linguagem gerada por G.

Este exemplo é simples porque todas as células da matriz foram preenchidas. Isto nem sempre acontece, como o podemos ver no exemplo seguinte.

Seja G′={{S,A},{a,b},P,S} com P={ SA B, Sb, Aa BS A}

S
 
B
 
S
 
  B 
AASA
A
aabaa

De reparar que neste exemplo não se consegue preencher todas as células da matriz. No entanto as células preenchidas levam mesmo assim a que se coloque o símbolo inicial no topo da matriz. A palavra é assim aceite. Na linha 4 só se consegue colocar o B graças a regra BS A. De seguida só se consegue colocar o S na linha 3 porque se tem a regra SA B. Neste caso o A provem de M[5,2] e B de M[4,3]. O caso realçado na matriz corresponde ao caso da aplicação da regra BS A com A retirado de M[5,5]. Finalmente consegue-se colocar S em M[1,1] graças ao A de M[5,1] e o B de M[2,2].

Input

Na primeira linha é introduzida a palavra por reconhecer. Esta palavra só é constituida por caracter do alfabeto Σ={a,…, z} e tem por comprimento máximo 50 caracteres. Assume-se que o conjunto de não-terminais é N={A,B, … S , …, Z} em que se destaca o simbolo S que assumiremos como sendo sempre o símbolo inicial.

A segunda linha apresenta o número m de regras de produções da gramática considerada.

As restantes m linhas introduzem as m regras de produção. Cada uma destas produções tem o formato seguinte N -> a1 a2 a3an com N não terminal e ai ∈ (N ∪ Σ) e cada ai é separado do aj seguinte por um espaço único.

Output

O output é constituida por uma única linha contendo:

Sample Input 1

abbabba
7
S -> S F
S -> a
A -> C C
A -> S S
A -> C S
C -> b
F -> A S

Sample Output 1

YES

Sample Input 2

aaabbabaaaabba
8
S -> S F
S -> a
A -> C G
A -> S S
A -> C S
C -> b
F -> A S
G -> C A

Sample Output 2

NO

This document was translated from LATEX by HEVEA.