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

Question

我知道泵引理可以用来确定一种语言是否是一种规则语言，上下文无关的语言，下推自动机等等。然而，我想知道在判断一种特定语言是哪一种语言时是否有什么窍门，或者某些语言的一般倾向？

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

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} \ 1}*，其中w^R是W}
5. L = {w2w w元素的反式，1}*}
6. L = {w2w^R = {0，1}*的w元素，其中w^R与W}

相反

答案是：

DPDA不是有限自动机，不是DPDA是空堆栈，而是由最终状态的stack.

• Finite

• 有限自动机，而不是由空的

自动机来实现的，也不是由空栈的

• 实现的，而不是DPDA

• ，没有任何DPDA

H 125 DPDA按最终状态，而不是FSAH 226G 227/code>

谢谢!

Answer 1

有一些简单的观点，您可以通过查看一种语言来判断它是哪一种语言(P.S:这些不是声明的规则，而是从这些语言的定义中派生出来的)。

1. 检查语言是否是有限的。有限语言是有限自动机所接受的语言。例如，L={a^n ^m\m\ n+m<100}或L= {a^n ^n\n\ n<50}。这些例子可能看起来是上下文无关的语言，但实际上它们是有限的，因此被有限的automata.
2. Check所接受，无论语言中给出的条件是否涉及单一的比较。如果它涉及多个比较，那么它既不是常规的，也不是无上下文的。然后是上下文敏感的语言。例如，对于L={a^n ^n^n\n\x n>1}和L= {a^n ^n^m^m\ m>n}，都是存在多个比较的情况。在第一种情况下，它存在于语言体中，而在第二种情况下，如果你对掌上电脑的设计有一定的了解，那么在language.
3. Distinguish的情况下，一种身体上的比较和另一种比较是很容易的。如果语言包含更改状态的明确点，则为DPDA，否则即为PDA。
4. 如果上下文无关的语言包含一个相等的条件，如L={w.wR w元素{0,1}* }或L ={ a^nb^n\n n>1}，则PDA被空堆栈和最终状态接受，但如果该条件是不平等的，则需要检查堆栈是否为空。
5. 尝试可视化堆栈，并使用该堆栈尝试可视化给定的比较是否可以进行。为了使一种语言是上下文无关的，应该只使用一个堆栈来处理comparison.
6. In大小写，该语言非常复杂，可以猜测它是普通的还是上下文无关的，那么它必须是上下文敏感的。没有任何方法可以直接判断一种语言是R.E还是上下文敏感的，因此假设每一种语言都可以用set-builder形式编写，并且不是规则的或上下文无关的语言是context-sensitive.

。

正如我前面所说的，这些不是陈述的规则或事实，而是从这些语言的定义中衍生出来的一些要点。为了快速猜出答案，试着根据这些规则练习一些语言。