cyk

CYK – tai algoritmas, skirtas patikrinti, ar eilutė priklauso tam tikrai gramatikai (dažnai be konteksto), naudojant dinaminį programavimą. Jis veikia su Chomsky normalios formos gramatikomis.

Pagrindinė idėja: Algoritmas užpildo lentelę, kurioje kiekviena ląstelė rodo neterminalus, galinčius generuoti tam tikrą eilutės dalį.

Pavyzdys:
Tarkime, gramatika:
1. S → AB | BC
2. A → BA | a
3. B → CC | b
4. C → AB | a

Tikriname eilutę „baaba“:

1. Lentelėje pirmoji įstrižainė (ilgio 1 požymiai):
- Pozicija 1 („b“): B
- Pozicija 2 („a“): A, C
- Pozicija 3 („a“): A, C
- Pozicija 4 („b“): B
- Pozicija 5 („a“): A, C

2. Tolimesnės įstrižainės (ilgio 2, 3, …) skaičiuojamos derinant gretimas ląsteles pagal gramatikos taisykles.

3. Jei viršutinėje lentelės ląstelėje yra pradinis simbolis S, eilutė priklauso gramatikai.

Pritaikymas: naudojamas sintaksinei analizei, kalbos apdorojime, kompiliatorių teorijoje.

Įrašas
Paaiškinimas	CYK – tai algoritmas, skirtas patikrinti, ar eilutė priklauso tam tikrai gramatikai (dažnai be konteksto), naudojant dinaminį programavimą. Jis veikia su Chomsky normalios formos gramatikomis. Pagrindinė idėja: Algoritmas užpildo lentelę, kurioje kiekviena ląstelė rodo neterminalus, galinčius generuoti tam tikrą eilutės dalį. Pavyzdys: Tarkime, gramatika: 1. S → AB | BC 2. A → BA | a 3. B → CC | b 4. C → AB | a Tikriname eilutę „baaba“: 1. Lentelėje pirmoji įstrižainė (ilgio 1 požymiai): - Pozicija 1 („b“): B - Pozicija 2 („a“): A, C - Pozicija 3 („a“): A, C - Pozicija 4 („b“): B - Pozicija 5 („a“): A, C 2. Tolimesnės įstrižainės (ilgio 2, 3, …) skaičiuojamos derinant gretimas ląsteles pagal gramatikos taisykles. 3. Jei viršutinėje lentelės ląstelėje yra pradinis simbolis S, eilutė priklauso gramatikai. Pritaikymas: naudojamas sintaksinei analizei, kalbos apdorojime, kompiliatorių teorijoje.
	Išsaugoti

Jūsų pataisymai bus išsiųsti moderatorių peržiūrai, jei informacija tikslesnė/taisyklingesnė
ji bus patalpinta vietoj esamos.