automata - 下推自动机定义

Question

我对 PDA 的正式描述（下推自动机）感到很困惑

如果我们记下 L(M)，这意味着 PDA M 可以识别语言 L，对吗？

那么，L(M)* 表示 PDA M 识别出 L* 对吗？

但是 L* 是什么意思？PDA 如何识别 L 的无限组合？

Answer 1

L(M)* 表示 PDA M 识别出 L* 对吗？

不！它是指由 PDA M 识别的语言中有效的任意数量的句子（包括零个）串联构成的语言。

鉴于 L(M) 是上下文无关的，很容易证明 L(M)* 也是上下文无关的。

要构造 L(M)* ，只需获取 L(M) 的所有语法，从 L(M) 中获取起始符号 S 并添加两个新产生式R -> S R，R -> empty其中 R 是 L(M)* 的起始符号。

所以，鉴于 L(M)* 是上下文无关的，那么就有一些 PDA 可以识别它。如果你可以为 L(M) 构造一个 PDA，那么构造一个 L(M)* 的 PDA 应该是微不足道的，因为它几乎与 L(M) 相同，只是有两个额外的产生式。