2

语言 L 满足常规语言的抽引引理和上下文无关语言的抽引引理。以下关于 L 的陈述哪些是正确的？

A.L 必然是一种常规语言。

B. L 必须是 CFL 但不是正则。

C. L 必然是非常规的。

D. 无

我会清楚我怀疑的地方。如果 L 满足正则语言的抽引引理，那么它不一定是正则的。与无上下文相同。所以它可以是常规的或非常规的。节能灯或非节能灯。给出的答案是B，但在我看来应该是D。谁能指出我遗漏了什么。

4

2 回答 2

1

答案 B 肯定不对。试试 Σ* 语言，它是绝对规则的，绝对是上下文无关的。它还通过了两个泵引理的条件。因此，该语言绝对不是上下文无关但不规则的。

两个抽水引理都给出了语言是正则或无上下文的必要条件，而不是那些语言是正则或无上下文的充分条件。因此，如果一种语言同时通过了这两个引理，它可能是常规的并且可能是无上下文的，但不能保证一定是这种情况。

我很确定 D 是这里的正确选择。

希望这可以帮助！

于 2014-12-30T01:43:53.527 回答
0

暗示：

  1. 抽引引理：¬q → ¬p其中，q 是抽引引理，p 是常规语言。这Contrapositive就是说，如果一种语言不满足抽引引理，那么它就不能是常规语言。它总是正确的。
  2. 那么， 也是正确的p → q。这意味着如果一种语言是规则的，那么它总是满足抽引引理。

另外，请注意，根据介词逻辑，它的逆 ¬p → ¬q和逆q → p不一定是真的。

于 2018-12-14T08:34:13.793 回答