所以我有一个无法解决的上下文无关语法问题 . 这不是等级或其他东西，所以不要担心 .
问题是这样的：
有一个上下文无关语法，看起来像S - > S1 | S2 S1 - > aS1B | B S2 - > S2aB | B B - > bS | b任务是编写一个函数（用任何编程语言）count_words（n） . 函数需要返回“n”长度的单词数，这些单词在此上下文自由语言中“涉及” . *假设我用count_words（3）调用函数，函数必须返回长度为3的可能单词的数量（在上下文自由语言中） . 那将是：bab，abb，aab等 .
任何人都可以帮助我吗？我根本不知道......假设这并不难，但我不能强迫自己思考正确的方法 .
1 回答
您需要模拟语法 . 给定终端
a和b，构造一个接受您的语言的自动机 . 由于您提供的语法是左递归语法，因此可以选择构造类似于LR解析器的下推自动机 . 在每个符号推送之后，如果生成的解析堆栈可以缩减为起始符号，则语法可以接受该字符串 . 继续这个直到所需的字符串长度 .基本上你是在模拟自动机并进行分支，因为你会在减少解析堆栈之后尝试使用所有可能的输入进行模拟 .
您可以避免完全构造自动机，只需查看给定每个状态的可能规则 .