我正在为我的理论课做硬件作业，遇到了一个我什至不知道从哪里开始的问题。我们正在介绍下推自动机部分。
“让 L1 是一种上下文无关语言，而 L2 是规则的。证明存在一种算法来确定 L1 和 L2 是否有无限数量的共同元素。”
我不知道如何解决这个问题。我无法让我的头脑理解这个想法。我确实知道常规语言不允许模棱两可，我想知道这是否是这个问题需要考虑的事情。此外，由于它位于“下推式自动机”部分，我假设它可能需要创建 npda 或 pda。谁能至少引导我朝着正确的方向前进。不是要求硬件解决，而是寻求硬件帮助！
给定 L1 的 PDA A1 和 L2 的 DFA A2，构造 A3，它使用笛卡尔积机器构造识别 L1 和 L2 的交集，就像在两个 DFA 之间一样。正式的结构有点混乱，但基本上你有新的状态来跟踪旧状态的组合并根据需要添加转换/堆栈更改。
使用标准构造从 A3 构造 CFG G3。同样，证明是混乱的，你最终会得到混乱的语法，但这也可以做到。
从 G3 中删除无用的变量、空和单位产品。如果您习惯于乔姆斯基范式 (CNF)，这基本上是一种类似的过程。
创建一个非终结符的依赖图。如果依赖图中存在循环，则 G3 的语言是无限的。
由于 G3 是 L1 和 L2 之间的共同词的语法，因此如果 L1 和 L2 有无限多的共同词，则 G3 产生无限多的词。