資料結構
網路
關係型資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究關於CYK演算法在上下文無關文法中的應用
CKY代表Cocke-Kasami-Younger。它是最早的識別和解析演算法之一。標準版本的CKY只能識別由喬姆斯基正規化(CNF)的上下文無關文法定義的語言。
也可以擴充套件CKY演算法來處理一些不屬於CNF的文法（難以理解）。
基於“動態規劃”方法 -
從子解決方案組合構建解決方案
它直接使用語法。
演算法
Begin
for ( i = 1 to n do )
Vi1 { A | A → a is a production where i th symbol of x is a }
for ( j = 2 to n do )
for ( i = 1 to n - j + 1 do )
Begin
Vij = ϕ
For k = 1 to j - 1 do
Vij = Vij ∪ { A | A → BC is a production where B is in Vik and C is in V(i + k)(j - k) }
End
End示例
CYK演算法用於確定給定的上下文無關文法是否生成給定的字串。
給定的上下文無關文法(CFG) -
S --> AB | BC A --> BA | a B --> CC | b C --> AB | a
需要檢查的字串是w =ababa
字串長度|w| = 5
| a | b | a | b | a |
|---|---|---|---|---|
| A→a C→a | B→b | A→a C→a | B→b | A→a C→a |
| S→AB CεAB | S→BC A→BA | S→AB CεAB | S→BC A→BA | |
| BεC | S→AB C→Ab | BεCC | ||
| B→CC | B→CC | |||
| S,C,A |
S出現在最後一個單元格中，因此字串有效。
解釋
第一個字母a可以透過變數A或C找到。對於b，變數B可以找到終結符b。因此，B將位於第一行第二列。
對於第二行，我們需要構成兩個終結符的組合，這將減少一個單元格。在第二行中，第一行的單元格將被配對，例如我們將有ab、ba、ab、ba。
因此，我們需要找到可以找到ab的變數，並將該變數放在第二行第一列。對於a，我們有A、C可以找到它。對於b，我們有B。因此，對於ab，它將按順序配對，例如AB、CB。
現在我們需要檢查給定的語法中是否存在這兩個產生式AB、CB。AB可以透過S和C找到。
因此，S、C產生式將放置在那裡。
類似地，對於ba，它將使用B表示b，使用A、C表示a。因此，產生式將是BA、BC。並且BA、BC可以透過產生式S、A找到。因此，這將放在第二行第二列。然後第二行第三列是ab，與第二行第一列相同。第二行第四列將是ba，與第二行第二列相同。
類似地，接下來的行需要找到終結符aba、bab、aba，並且按順序可以找到它們的變數將是B表示aba，S、C表示bab，B表示aba。
現在第四行將四個終結符組合在一起，例如abab、baba。並且它的產生式將是B。在最後一個術語ababa中，所有五個都將組合在一起，並且它的產生式將是S、C、A。
如果最後一個是S，即起始狀態，則接受給定的字串。因此，對於給定的字串，成員資格為真。
此外，您還需要檢視如果將三個終結符組合在一起，則其產生式可以找到為(ab a)或(a ba)。類似地，對於四個組合在一起的終結符(a bab)或(aba b)或(ab ab)。類似地，對於五個(ab aba)或(aba ba)或(abab a)……
7K+ 次瀏覽
