automation - 如何确定这些语言属于哪个类？

Question

{WW} - 可判定但不是上下文无关
{WW^R} - 上下文无关，但不是正则
Σ* - 正则语言
你如何确定它们属于哪个类？

Answer 1

可能我的回答对你有帮助：

L ₁ = {ww | w ∈ {a, b} ^* }

不是上下文无关语言，因为（下推自动机）PDA 是不可能的（甚至是 Non-Deterministic-PDA ）。为什么？假设您首先推入w堆栈。要将第二个w与第一个匹配，w您必须以相反的顺序推送第一个w（或者您需要以w相反的顺序将第二个与堆栈内容匹配），而堆栈是不可能的（我们无法以相反的顺序读取输入）。虽然它是可判定的，因为它可以在有限步数之后 Turing Machine为 L _{1绘制一个总是一半的。}

L ₃ = {ww ^R | w ∈ {a, b} ^* }

语言 L ₃是一种非确定性上下文无关语言，因为它是可能的，但有限自动对于 L ₃n-PDA是不可能的。您还可以使用 Pumping Lemma for Regular Languages 来证明这一点。

Σ*- 常规语言（RL）

Σ*是正则表达式 (RE)，例如，如果Σ = {a, b} then RE is (a + b)* RE 仅适用于 RL。

我的问题中的示例可能对您更有帮助。