Cocke-Younger-Kasami (CYK)

Question

1

Cocke-Younger-Kasami (CYK)

BI
BI-AAG

asked Dec 5 '14

Anonymous

Ahoj,

dokázal by mi někdo poradit, jak pracovat s CYK algoritmem? Na přednášce ani ze slidů jsem to nepochopil (resp. ve slidech ani není řešení). Ve skriptech od Melichara jsem o tom nenašel ani zmínku.

Dokázal by mi prosím někdo vzorově vypočítat (i s postupem) třeba ten příklad se slidů (6. přednáška 26/36)? Byl bych vděčný. Jen pro jistotu je to tohle zadání:

Text aaba a BG G = ({S,A,B,C}, {a, b}, P, S), P:
S → AB | BC
A → BA | a
B → CC | b
C → AB | a

Děkuji mnohokrát.

add a comment

Accepted Answer

2

answered Dec 5 '14

Ondřej Máca
192 ●7 ●11 ●20

updated Dec 7 '14

Mělo by to být snad takto:

image description

Uděláš si čtvercovou tabulku o rozměrech délka řetězce + 1 a jedeš od spodu. Ty čísla vlevo značí délku řetězce. Takže když si vezmu řádek s č. 1 tak "a" vygeneruješ z Neterminálu A nebo C. To víš ze zadání. Obdobně "b".

Pak se díváš z čeho jdou vygenerovat řetězce délky 2. Nejdříve zjišťuješ z čeho vygenerovat "aa" prvni "a" lze vygenerovat z A nebo C druhe to ma samozrejme stejně, hledas tedy jestli je v pravidlech AA nebo AC nebo CA nebo CC. CC se da vygenerovat z B a tak je tam napises do "bunky" na radku s cislem 2. Pote zjisťuješ jestli lze vygenerovat "ab" stejně jako předtím a hledáš tedy v pravidlech neterminály AB a CB. To stejne i pro retezec "ba".

Pak jdeš o řádek výš a zjištuješ jestli jdou vygenerovat řetězce délky 3. Tedy "aab" a "aba". Ty se dají vygenerovat z řetězců délky 1 a 2 nebo 2 a 1. Díváš se tedy na 1. a 2. řádek. V prvním případě když zjišťuješ "aab" tak se díváš na první sloupec na 2. řádku - ten generuje "aa" a na 3. sloupec na 1. řádku - ten generuje "b". Hledáš tedy BB v pravidlech. To tam není, ale pak ještě musíš hledat kombinace terminálu na 1.řádku 1.sloupci - ty generují "a" a na 2. ř. 2. s. ty generují "ab".

Podobně pro řetězce délky 4. Hledáš kombinace neterminálu 3ř1s 1ř4s, 2ř1s 2ř 3s, 1ř1s 3ř2s. A pokud je v horním řádku S tak víš, že ten zadaný řetězec vygenerovat jde.

EDIT: teď jsem zjistil, že to je na avc - přednáška11 - čas 43

link