CYK-algoritme - Wikipedia
Die Cocke-Younger-Kasami (CYK) algoritme (alternatiewelik CKY genoem) bepaal of 'n string deur 'n gegewe konteksvrye grammatika genereer kan word en indien wel hoe dit gegenereer kan word. Dit staan bekend as sintaksontleding van die string. Die algoritme is 'n voorbeeld van dinamiese programmering.
Die standaard weergawe van CYK herken tale gedefinieer deur konteksvrye grammatikas in Chomsky-normaal-vorm (CNF). Aangesien enige konteksvrye grammatika sonder veel moeite in CNF omskep kan word, kan CYK gebruik word om enige konteksvrye grammatika taal te herken. Dit is ook moontlik om die CYK algoritme uit te brei om sommige konteksvrye grammatikas te hanteer wat nie in CNF geskryf is nie; dit kan gedoen word om verrigting te verbeter maar met die nadeel dat dit die algoritme moeiliker maak om te verstaan.
Die slegste asimptotiesetyd kompleksiteit van CYK is Θ(n3), waar n die lengte van die ontlede string is. Dit bring mee dat dit een van die mees effektiewe (in daardie terme) algoritmes vir herkenning van enige konteksvrye grammatika is. Daar is egter ander algoritmes wat beter verrigting sal verskaf vir sekere konteksvrye tale.
Die CYK algoritme is teoreties belangrik aangesien dit gebruik kan word om kontruktief te bewys dat die lidmaatskapprobleem vir konteksvrye tale beslegbaar is.
Die CYK algoritme vir die lidmaatskapprobleem is as volg:
Laat die inset string uit n letters bestaan, a1 ... an.
Laat die grammatika r terminaal en nie-terminaal simbole bevat R1 ... Rr. Hierdie grammatika bevat die deelversameling Rs wat die versameling begin simbole is.
Laat P[n,n,r] 'n boolse skikking wees. Inisialiseer al die element van P na vals.
Vir elke i = 1 tot n
Vir elke eenheid produksie Rj → ai, stel P[i,1,j] = waar.
Vir elke i = 2 to n -- Lengte van span
Vir elke j = 1 to n-i+1 – Begin van span
Vir elke k = 1 to i-1 -- Verdeling van span
Vir elke produksie RA -> RB RC
As P[j,k,B] en P[j+k,i-k,C] dan stel P[j,i,A] = waar
As enige van P[1,n,x] waar is (x word herhaal oor die versameling s, waar s al die indices vir Rs is)
Dan is string 'n lid van die taal
Anders is string nie 'n lid van die taal nie
Informeel gestel, die algoritme oorweeg elke moontlike deelstring van die string van letters en stel P[i,j,k] om waar te wees as die deelstring van letters beginnende by i met lengte j genereer kan word van Rk. Nadat dit die deelstringe van lengte 1 oorweeg het gaan dit aan na deelstringe van lengte 2, en so aan. Vir deelstringe met lengte 2 en groter oorweeg dit elke moontlike verdeling in twee helftes van die deelstring en maak seker of daar 'n produksie P → Q R is sodat Q ooreenkom met die eerste helfte en R met die tweede helfte. Indien wel, it records P as ooreenkomstig met die hele deelstring. Wanneer die proses voltooi is, is die sin herken deur die grammatika as die deelstring wat die hele string bevat ooreenkom met die begin simbool.