数据结构
网络
关系型数据库管理系统(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+ 次浏览
