Parskirina rêzimanek bê kontekst tê de analîzkirina rêzek sembolan li gorî rêzek rêzikên hilberînê yên ku ji hêla rêzimanê ve hatine destnîşan kirin vedihewîne. Ev pêvajo di warên cihêreng ên zanistiya komputerê de, di nav de ewlehiya sîber, bingehîn e, ji ber ku ew dihêle ku em daneyên sazkirî fam bikin û manîpule bikin. Di vê bersivê de, em ê algorîtmaya parskirina rêzimanek bê-contekst rave bikin û tevliheviya dema wê nîqaş bikin.
Algorîtmaya ku herî zêde tê bikar anîn ji bo parskirina rêzimanên bê-contekst algorîtmaya CYK e, ku navê wê ji dahênerên wê Cocke, Younger, û Kasami re tê gotin. Ev algorîtma li ser bernameya dînamîk e û li ser prensîba parskirina jêrîn-jor dixebite. Ew tabloyek parsek çêdike ku hemî parsekên gengaz ên ji bo binerdeyên têketinê temsîl dike.
Algorîtmaya CYK bi vî rengî dixebite:
1. Tabloyek parsek bi pîvanên nxn dest pê bikin, ku n dirêjahiya rêzika têketinê ye.
2. Ji bo her sembola termînalê ya di rêzika têketinê de, şaneya têkildar a di tabloya parsê de bi sembolên netermînalê yên ku wê çêdikin tije bikin.
3. Ji bo dirêjahiya her binerxek l ji 2 heta n, û her pozîsyona destpêkê i ji 1 heta n-l+1, jêrîn bikin:
yek. Ji bo her xala dabeşkirinê p ji i heta i+l-2, û her qaîdeya hilberînê A -> BC, kontrol bikin ka di şaneyên (i, p) û (p+1, i+l-1) de sembolên bêdawî B û C hene. , bi rêzê ve. Ger wusa be, A-yê li şaneyê zêde bike (i, i+l-1).
4. Ger nîşana destpêk a rêzimanê di şaneya (1, n) de hebe, rêzika têketinê dikare ji rêzimanê were wergirtin. Wekî din, ew nikare.
Tevliheviya demê ya algorîtmaya CYK O(n^3 * |G|) ye, ku n dirêjahiya rêzika têketinê ye û |G| qebareya rêzimanê ye. Ev tevlihevî ji xelekên hêlîn ên ku ji bo dagirtina tabloya parsê têne bikar anîn çêdibe. Algorîtm hemî xalên dabeşkirinê yên gengaz û qaîdeyên hilberînê yên ji bo her dirêjahiya binesaziyê dikole, di encamê de tevliheviya dema kub çêdibe.
Ji bo ronîkirina algorîtmayê, rêzimana jêrîn a bê-conteks binirxînin:
S -> AB | BC
A -> AA | yek
B -> AB | b
C -> BC | c
Û rêzika têketinê "abc". Tabloya parsek ji bo vê nimûneyê dê wiha xuya bike:
| 1 | 2 | 3 |
——-|—–|—–|—–|
1 | A,S | B,C | S |
——-|—–|—–|—–|
2 | | B,C | A |
——-|—–|—–|—–|
3 | | | C |
——-|—–|—–|—–|
Di vê tabloyê de, di şaneya (1, 3) de nîşana destpêkê S heye, ku nîşan dide ku rêzika têketinê "abc" dikare ji rêzimanê hatî destnîşan kirin.
Algorîtmaya parskirina rêzimanek bê kontekst, wek algorîtmaya CYK, dihêle ku em daneyên sazkirî analîz bikin û fam bikin. Ew bi avakirina tabloyek parsek û kontrolkirina deranên derbasdar li gorî rêzikên hilberîna rêzimanê tevdigere. Tevliheviya demê ya algorîtmaya CYK O(n^3 * |G|) ye, ku n dirêjahiya rêzika têketinê ye û |G| qebareya rêzimanê ye.
Pirs û bersivên din ên vê dawiyê di derbarê Tevlîheviyê:
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
- Ma pola tevliheviya P binkomek pola PSPACE ye?
- Ma em dikarin îsbat bikin ku çîna Np û P yek in bi dîtina çareseriyek polînomî ya bikêr ji bo her pirsgirêkek bêkêmasî ya NP li ser TM-ya diyarker?
- Ma pola NP dikare bi çîna EXPTIME re wekhev be?
- Di PSPACE de pirsgirêk hene ku ji bo wan algorîtmaya NP-ya naskirî tune?
- Ma pirsgirêkek SAT dikare bibe pirsgirêkek tevahî NP?
- Ma dibe ku pirsgirêk di pola tevliheviya NP de be heke makîneyek ziravî ya ne diyarker hebe ku dê di dema pirnomî de wê çareser bike
- NP çîna zimanên ku xwedan verastkerên dema pirnomî ne
- Ma P û NP bi rastî heman çîna tevliheviyê ne?
- Ma her çarçoveyek zimanek azad e di pola tevliheviya P de?
Pir pirs û bersivan di Complexity de bibînin