Cocke-Younger-Kasami (CYK)

Question

1

Cocke-Younger-Kasami (CYK)

BI
BI-AAG

asked 2014-12-05 13:17:51 +0100

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.

edit retag flag offensive close delete

Accepted Answer

2

answered 2014-12-05 16:13:42 +0100

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

updated 2014-12-07 12:30:36 +0100

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

edit flag offensive delete publish link

Comments

Alebo tu http://www.youtube.com/watch?v=4YyiOjMUpSQ&feature=youtu.be od 1:09

gandalf ( 2014-12-07 12:32:20 +0100 )edit

super, máš odkazy i na další části?

Ondřej Máca ( 2014-12-07 14:10:11 +0100 )edit

https://www.fit-wiki.cz/%C5%A1kola/p%C5%99edm%C4%9Bty/bi-aag/konzultace

gandalf ( 2014-12-07 14:15:59 +0100 )edit

díky

Ondřej Máca ( 2014-12-07 14:35:06 +0100 )edit

Answer 2

2

answered 2014-12-06 20:05:28 +0100

ruzicja7
53 ●2 ●2 ●7

updated 2014-12-06 20:06:14 +0100

Osobně jsem se to učil z téhle reference:

CYK Algorithm

Na základní pochopení to bohatě stačí!

edit flag offensive delete publish link

Cocke-Younger-Kasami (CYK)

2 Answers

Comments

Your answer

Question tools

Stats

Related questions