无上下文文法中的单词计数

Question

无上下文文法中的单词计数

4

我有一个与上下文无关语法相关的问题，但我没有解决。这不是为了成绩或其他什么事情，所以不用担心。

问题如下：

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

S -> S1 | S2

S1 -> aS1B | B

S2 -> S2aB | B

B -> bS | b

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

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

有人能帮我吗？我完全不知道...也许不难，但我无法强迫自己思考正确的方式。

- dperitch

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dervall · Accepted Answer

你需要模拟语法。给定终端符号 a 和 b，构建一个接受你的语言的自动机。由于你提供的语法是左递归的语法，一个选项是构建一个类似于 LR 解析器的下推自动机。在每个符号推送后，如果结果解析堆栈可以被规约为起始符号，则该字符串可以被语法接受。重复此过程直到达到所需的字符串长度。

基本上，你正在模拟自动机并分支出去，因为你将尝试在缩小解析栈后使用所有可能的输入进行模拟。

你可能可以避免完全构建自动机，只需查看每个状态下可能的规则。