algorithm - 借助堆栈确定该单词来自语言

Question

借助堆栈确定单词来自特定语言的算法是什么？

我知道我可以将单词逐个符号放入堆栈中，同时我可以记录有关符号的任何所需信息，但这与仅迭代单词没有什么不同。

Answer 1

如果语言由 context-free grammar 定义，特定单词的成员资格可以通过所谓的 CYK-Algorithm 有效地确定。 .

上例中给出的语言可以用以下上下文无关语法表示，其中 epsilon 表示空字符串。

S -> epsilon | aSb | ab

更新

要使 CYK 算法适用，语法必须为 Chomsky normal form ;对于上面的语法，可以按如下方式完成。

S -> epsilon | AT | AB
T -> SB
A -> a
B -> b

在此公式中，A 和 B 是终结符 a 和 b 的人工非终结符； T 是一个人工变量，因为每个右侧最多可以包含两个非终结符而引入。