context-free-grammar - 计算上下文无关语法中的单词

Question

因此，我遇到了一个无法解决的上下文无关语法问题。这不是为了成绩什么的，所以不要担心。

问题是这样的：

有一个上下文无关的语法，看起来像

S -> S1 | S2

S1 -> aS1B | 乙

S2 -> S2aB | 乙

B -> bS | b

任务是编写一个函数（用任何编程语言）count_words(n)。函数需要返回长度为“n”的单词数，这些单词在这种上下文无关语言中“涉及”。

*假设我用 count_words(3) 调用函数，函数必须返回长度为 3 的可能单词的数量（在该上下文无关语言中）。那就是：bab、abb、aab 等。

任何人都可以帮助我吗？我完全不知道……假设这并不难，但我不能强迫自己以正确的方式思考。

Answer 1

您将需要模拟语法。给定终端a和b，构造一个接受您的语言的自动机。由于您提供的语法是左递归语法，因此可以选择构造一个类似于 LR 解析器的下推自动机。在每次符号推送之后，如果生成的解析堆栈可以减少到起始符号，则该字符串可以被文法接受。继续此操作，直到所需的字符串长度。

本质上，您是在模拟自动机并进行分支，因为您将在减少解析堆栈后尝试使用所有可能的输入进行模拟。

您可以避免完全构建自动机，而只需查看在给定每个状态时您处于哪些可能的规则。