上下文无关文法的CYK算法解释

  • Z时代
  • 2024-01-10
  • 分类：综合

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→a
C→a
乙→乙A→a
C→a
乙→乙A→a
C→a
S→AB
CεAB
S→BC
A→BA
S→AB
CεAB
S→BC
A→BA

BεCS→AB
C→Ab
BεCC

B→CCB→CC


S,C,A



S 出现在最后一个单元格中，因此该字符串有效。

解释

  • 第一个字母 a 可以通过变量 A 或 C 找到。对于 b，变量 B 可以找到终端 b。因此，B 将坐在第一排的第二个字段中。

  • 对于 row2 我们需要制作一对两个终端，它将减少 1 cell 。与第 2 行一样，第 1 行的字段将成为一对，就像我们将有 ab,ba,ab,ba 一样。

  • 因此，在此需要找到将找到 ab 的变量，并且该变量将放置在字段 row2, column1 中。对于 a，我们有 A、C 会找到它。对于 b，我们有 B。因此，对于 ab，它将像 AB、CB 一样按顺序生成一对。

  • 现在我们需要检查这两个产生式 AB, CB 在给定的语法中是否存在。AB 可以通过 S 和 C 找到。

  • 所以，S,C 生产将被放置在那里。

  • 同样，对于 ba，b 需要 B，a 需要 A，C。因此，生产将是 BA，BC。而 BA, BC 可以通过产生式 S, A 找到。所以，这将被放置在 row2, column2。然后再次 row2column3 是 ab so，与 row2column1 相同。而 row2column4 将与 row2Column2 相同。

  • 类似地，接下来的行需要找到终端 aba,bab,aba 并且按照顺序，可以找到它的变量将是 B 代表 aba，S,C 代表 bab，B 代表 aba。

  • 现在第 4 行的四个终端将作为 abab, baba 连接在一起。它的产量将是 B。 在最后一个学期 ababa 将所有五个都放在一起，它的产量将是 S、C、A。

  • 如果最后一个的 S 是起始状态，则接受给定的字符串。因此，对于给定的字符串，成员资格为真。

  • 此外，您还需要看到，如果将三个终端连接在一起，则可以将其生成为 (ab a) 或 (a ba)。类似地，对于四个终端，一个 (a bab) 或 (aba b) 或 (ab ab)。同样，对于五 (ab aba) 或 (aba ba) 或 (abab a) ....

以上是 上下文无关文法的CYK算法解释 的全部内容， 来源链接： utcz.com/z/322767.html

回到顶部