regex - 如何判断一种语言是否是常规语言、上下文无关语言、下推自动机等？

Question

我知道泵引理可用于确定一种语言是否是常规语言、上下文无关语言、下推自动机等。但是，我想知道在判断给定语言的语言类型方面是否有任何技巧是，或者某些语言​​的一般趋势？</p>

例如，仅通过查看语言描述就可以在下面的示例中说明语言是什么。

1. L = {(0^n)2(1^m) | n >= m }
2. L = {(0^n)2(1^m) | n >= 1, m >= 1, n + m <= 100 }
3. L = {(0^n)(1^m)2 | n >= 1, m >= 1, n + m <= 100 }
4. L = {ww^R} | {0, 1}* 的 w 元素，其中 w^R 是 W} 的倒数
5. L = {w2w | {0, 1}*} 的 w 元素
6. L = {w2w^R | {0, 1}* 的 w 元素，其中 w^R 是 W} 的倒数

答案是：

1. 不是有限自动机，不是空堆栈的 DPDA，而是最终状态的 DPDA
2. 有限自动机，但不是空堆栈的 DPDA。
3. 有限自动机，也是空栈的 DPDA
4. 是 PDA，但不是 DPDA
5. 不是任何 DPDA
6. 空堆栈的 DPDA 和最终状态的 DPDA，而不是 FSA

谢谢！

标签： regexpushdown-automaton

Answer 1

您可以通过查看可以帮助您确定它是哪种语言的语言来检查一些简单的点（PS：这些不是规定的规则，而是源自这些语言的定义）。

1. 检查语言是否有限。有限语言意味着它被有限自动机接受。例如 L= {a^nb^m | n+m<100} 或 L={a^nb^n | n<50}。这些示例可能看起来与上下文无关的语言，但实际上它们是有限的，因此被有限自动机接受。
2. 检查语言中给出的条件是否涉及单一比较。如果它涉及多个比较，则它既不是常规的也不是无上下文的。然后是上下文相关的语言。例如 L= {a^nb^nc^n | n>1} 和 L={a^nb^nc^m | m>n} 两者都是存在多个比较的情况。在第一种情况下，它出现在语言的主体中，在第二个例子中，一个身体比较和另一个语言条件比较。
3. 如果您了解 PDA 的设计知识，就很容易区分 PDA 和 DPDA。如果语言包含改变状态的明确点，那么它就是 DPDA，否则就是 PDA。
4. 如果上下文无关语言涉及一个相等的条件，例如 L={w.wR | {0,1}* } 的 w 元素或 L ={ a^nb^n| n>1}，则PDA被空堆栈和最终状态接受，但如果条件不等，则需要检查堆栈是否为空。
5. 尝试可视化堆栈并使用该堆栈尝试可视化是否可以进行给定的比较。对于无上下文的语言，应该只使用一个堆栈进行比较。
6. 如果语言足够复杂，可以猜测它是常规语言还是无上下文的，那么它必须是上下文相关的。没有任何方法可以直接判断一种语言是 RE 还是上下文敏感的，因此假设可以以 set-builder 形式编写并且不是常规或上下文无关的每种语言都是上下文敏感的。

正如我之前所说，这些不是规定的规则或事实，而只是从这些语言的定义中得出的一些观点。为了快速猜测，只需尝试根据这些规则练习一些语言。