1 CT–200: Fundamentos de Automata e Linguagens Formais Gramáticas Livres de Contexto - Algoritmo CYK Gabriel Dischinger de Lima Paulo Honda Ota Professor: Carlos Henrique Q. Forster Nov/2016 CT-200

2 PROBLEMA A SER RESOLVIDODada uma Gramática Livre de Contexto G = (V, ∑ ,P , S), e uma cadeia w, onde: V é o conjunto finito de variáveis ∑ é o conjunto finito de simbolos terminais (o alfabeto) P é o conjunto finito de regras/produções S é o símbolo inicial sendo V and ∑ disjuntos A cadeia w pertence a linguagem gerada pela gramática G? A cadeia w é aceita/reconhecida? Nov/2016 CT-200

3 O ALGORITMO CYK Desenvolvido de maneira independente, em meados dos anos 60 início dos 70, por três pesquisadores: Cocke Younger Kasami O algoritmo trabalha sobre uma GLC (Gramática Livre de Contexto) na Forma Normal de Chomsky (pré-requisito) Usa programação dinâmica (a solução é encontrada a partir de sub soluções previamente calculadas e memorizadas) para reconhecer se a cadeia é gerada pela gramática. Nov/2016 CT-200

4 Forma Normal de ChomskyUma gramática G está na Forma Normal de Chomsky se todas as suas regras/produções seguirem uma das seguintes formas: Onde A,B,C são variáveis (símbolos não terminais), a é um símbolo terminal (representa um valor constante), S é a variável inicial e e é a cadeia vazia. Além disso nem B nem C podem ser a variável inicial. Nov/2016 CT-200

5 CYK - IDEIA PRINCIPAL Em termos informais, este algoritmo considera todas as subpalavras (substrings) da cadeia w e define T [i, j, k] para ser verdadeiro se a subpalavra a partir de i de comprimento j pode ser gerada a partir da variável Vk. A matriz booleana T é uma representação da matriz triangular M, que é preenchida de baixo para cima com símbolos variáveis. Uma vez consideradas as subpalavras de comprimento 1, ele passa para subpalavras de comprimento 2, e assim por diante. Nov/2016 CT-200

6 CYK - IDEIA PRINCIPAL 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 Y → BC ∈ G tal que B corresponde à primeira parte e C corresponde à segunda parte da subpalavra. Se assim for, ele registra Y como combinando toda a subpalavra. Quando esse processo for concluído, a cadeia w será considerada gerada pela gramática se o símbolo de partida S foi registrado para a palavra inteira. Nov/2016 CT-200

7 CYK - IDEIA PRINCIPAL Ou seja:O algoritmo realiza uma análise ascendente (bottom-up) das cadeias; O algoritmo parte da cadeia a ser analisada e regride nas produções formando uma tabela triangular; A cadeia é aceita se quando o triângulo estiver completo o símbolo de partida da gramática estiver no topo do mesmo. Nov/2016 CT-200

8 CYK - CONSTRUÇÃO DA MATRIZ TRIANGULARCada linha da matriz corresponde a um tamanho de subpalavra (substring) Xi,i corresponde ao conjunto de variáveis Y tais que Y → wi é uma produção da gramática G Xi,j = U { Y | Y → BC ; B Vi,k e C  Vk+1,j } k  {i,j+1,...j-1} Nov/2016 CT-200

9 CYK - CONSTRUÇÃO DA MATRIZ TRIANGULARNov/2016 CT-200

10 CYK - CONSTRUÇÃO DA MATRIZ TRIANGULAR“Esquema da Roldana” Nov/2016 CT-200

11 1) Xi,i corresponde ao conjuntoCYK – EXEMPLO 1 Dada a gramática: S → AA | AS | b A → SA | AS | a A cadeia abaab é reconhecida? 1) Xi,i corresponde ao conjunto de variáveis Y tais que Y → wi é uma produção da gramática G Nov/2016 CT-200

12 2) Aplicar o “esquema da roldana”CYK – EXEMPLO 1 Dada a gramática: S → AA | AS | b A → SA | AS | a A cadeia abaab é reconhecida? 2) Aplicar o “esquema da roldana” Xi,j = U { Y | Y → BC ; B Vi,k e C  Vk+1,j } k  {i,j+1,...j-1} Nov/2016 CT-200

13 2) Aplicar o “esquema da roldana”CYK – EXEMPLO 1 Dada a gramática: S → AA | AS | b A → SA | AS | a A cadeia abaab é reconhecida? 2) Aplicar o “esquema da roldana” Xi,j = U { Y | Y → BC ; B Vi,k e C  Vk+1,j } k  {i,j+1,...j-1} Nov/2016 CT-200

14 2) Aplicar o “esquema da roldana”CYK – EXEMPLO 1 Dada a gramática: S → AA | AS | b A → SA | AS | a A cadeia abaab é reconhecida? 2) Aplicar o “esquema da roldana” Xi,j = U { Y | Y → BC ; B Vi,k e C  Vk+1,j } k  {i,j+1,...j-1} Nov/2016 CT-200

15 2) Aplicar o “esquema da roldana”CYK – EXEMPLO 1 Dada a gramática: S → AA | AS | b A → SA | AS | a A cadeia abaab é reconhecida? 2) Aplicar o “esquema da roldana” Xi,j = U { Y | Y → BC ; B Vi,k e C  Vk+1,j } k  {i,j+1,...j-1} Nov/2016 CT-200

16 CYK – EXEMPLO 2 Entendendo melhor b a a b a Dada a gramática:S → AB | BC A → BA | a B → CC | b C → AB | a A cadeia baaba é reconhecida? Fazer no quadro Nov/2016 CT-200

17 CYK – EXEMPLO 2 Entendendo melhor b a a b a B A,C Dada a gramática:S → AB | BC A → BA | a B → CC | b C → AB | a 1) Avaliando as produções da gramática que geram as subpalavras / subcadeias de tamanho 1 Nov/2016 CT-200

18 CYK – EXEMPLO 2 Entendendo melhor b a a b a B A,C S,A S,CDada a gramática: S → AB | BC A → BA | a B → CC | b C → AB | a 2) Avaliando as produções que geram as subpalavras / subcadeias de tamanho 2: ba, aa, ab, ba Nov/2016 CT-200

19 CYK – EXEMPLO 2 Entendendo melhor b a a b a B A,C S,A S,C -Dada a gramática: S → AB | BC A → BA | a B → CC | b C → AB | a 3) Avaliando as produções que geram as subpalavras / subcadeias de tamanho 3: baa = b,aa / ba,a aab = a,ab / aa,b aba = a,ba / ab,a Nov/2016 CT-200

20 CYK – EXEMPLO 2 Entendendo melhor b a a b a B A,C S,A S,C - S,A,CDada a gramática: S → AB | BC A → BA | a B → CC | b C → AB | a 4) Avaliando as produções que geram as subpalavras / subcadeias de tamanho 4: baab = b,aab / ba,aab / baa,b aaba = a,aba / aa,ba / aab,a Nov/2016 CT-200

21 CYK – EXEMPLO 2 Entendendo melhor b a a b a B A,C S,A S,C - S,A,CSímbolo S presente. Cadeia é reconhecida! S,A,C Dada a gramática: S → AB | BC A → BA | a B → CC | b C → AB | a 5) Avaliando as produções que geram a cadeia de tamanho 5 baaba = b,aaba ba,aba baa,ba baab,a Nov/2016 CT-200

22 CYK – Implementação Código fonte Nov/2016 CT-200

23 CYK – Implementação Código fonte Nov/2016 CT-200

24 CYK – Implementação Código fonte Nov/2016 CT-200

25 CYK – Implementação Nov/2016 CT-200

26 CYK – Implementação Nov/2016 CT-200

27 Nov/2016 CT-200

28 Nov/2016 CT-200

29 Nov/2016 CT-200

30 Nov/2016 CT-200

31 Nov/2016 CT-200

32 Nov/2016 CT-200

33 Nov/2016 CT-200

34 REFERÊNCIAS J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Second Edition, Addison Wesley, 2001 T.A. Sudkamp, An Introduction to the Theory of Computer Science Languages and Machines, Third Edition, Addison Wesley, 2006 P. B.Menezes, Linguagens Formais e Autômatos, Terceira Edição, Sagra Luzzatto, 2000 Nov/2016 CT-200