如何判断一种语言是常规语言、上下文无关语言、下推自动机等？
How to tell whether a language is a regular language, context free language, Push down Automata, etc?
我知道pumping lemma可以用来判断一种语言是Regular Language, Context Free Language, Pushdown Automata等等。但是，我想知道是否有什么技巧可以判断是什么类型的给定语言是什么语言，或者某些语言的一般趋势？
例如，是否可以通过查看语言描述来判断以下示例中的语言是什么？
- L = {(0^n)2(1^m) | n >= m }
- L = {(0^n)2(1^m) | n >= 1, m >= 1, n + m <= 100 }
- L = {(0^n)(1^m)2 | n >= 1, m >= 1, n + m <= 100 }
- L = {ww^R} | {0, 1}* 的 w 元素，其中 w^R 是 W}
的倒数
- L = {w2w | {0, 1}*}
的 w 元素
- L = {w2w^R | {0, 1}* 的 w 元素，其中 w^R 是 W}
的倒数
答案是：
- 不是有限自动机，不是空栈的 DPDA，而是最终状态的 DPDA
- 有限自动机，但不是空栈的 DPDA。
- 有限自动机，也是空栈的DPDA
- 是PDA，不是DPDA
- 没有任何 DPDA
- DPDA 为空堆栈，DPDA 为最终状态，而非 FSA
谢谢！
您可以通过查看一种语言来检查一些简单的要点，这些要点可以帮助您确定它是哪种语言（P.S：这些不是规定的规则，而是从这些语言的定义中派生出来的）。
- 检查语言是否有限。有限语言意味着它被有限自动机接受。例如 L= {a^n b^m | n+m<100} 或 L={a^n b^n | n<50}。这些示例可能看起来是上下文无关语言，但实际上它们是有限的，因此被有限自动机接受。
- 检查语言给出的条件是否涉及单比较。如果它涉及不止一次比较，那么它既不是 Regular 也不是 Context-free。然后是上下文相关的语言。例如L= {a^n b^n c^n | n>1} 和 L={a^n b^n c^m | m>n} 都是存在不止一个比较的情况。在第一种情况下，它存在于语言的主体中，在第二个示例中，一个比较在主体中，另一个比较在语言条件中。
- 如果您了解 PDA 的设计知识，则很容易区分 PDA 和 DPDA。如果该语言包含一个明确的改变状态的点那么它就是 DPDA 否则就是 PDA。
- 如果上下文无关语言涉及相等条件，如 L={w.wR | {0,1}* } 或 L ={ a^nb^n| 的 w 元素n>1}，则PDA被空栈和最终状态接受，但如果条件不等，则需要检查栈是否为空。
- 尝试可视化堆栈并使用该堆栈尝试可视化是否可以进行给定的比较。一种语言要是 Context-free，就应该只用一个栈来比较。
- 如果语言复杂到足以猜测它是Regular 还是context-free，那么它必须是context-sensitive。没有任何方法可以直接判断一种语言是 R.E 还是上下文相关的，因此假设可以以集合生成器形式编写并且不是常规或上下文无关的每种语言都是上下文-敏感。
正如我之前所说，这些不是规定的规则或事实，而只是从这些语言的定义中得出的一些要点。为了快速猜出，就试着根据这些规则练习一些语言吧。
我知道pumping lemma可以用来判断一种语言是Regular Language, Context Free Language, Pushdown Automata等等。但是，我想知道是否有什么技巧可以判断是什么类型的给定语言是什么语言，或者某些语言的一般趋势？
例如，是否可以通过查看语言描述来判断以下示例中的语言是什么？
- L = {(0^n)2(1^m) | n >= m }
- L = {(0^n)2(1^m) | n >= 1, m >= 1, n + m <= 100 }
- L = {(0^n)(1^m)2 | n >= 1, m >= 1, n + m <= 100 }
- L = {ww^R} | {0, 1}* 的 w 元素，其中 w^R 是 W} 的倒数
- L = {w2w | {0, 1}*} 的 w 元素
- L = {w2w^R | {0, 1}* 的 w 元素，其中 w^R 是 W} 的倒数
答案是：
- 不是有限自动机，不是空栈的 DPDA，而是最终状态的 DPDA
- 有限自动机，但不是空栈的 DPDA。
- 有限自动机，也是空栈的DPDA
- 是PDA，不是DPDA
- 没有任何 DPDA
- DPDA 为空堆栈，DPDA 为最终状态，而非 FSA
谢谢！
您可以通过查看一种语言来检查一些简单的要点，这些要点可以帮助您确定它是哪种语言（P.S：这些不是规定的规则，而是从这些语言的定义中派生出来的）。
- 检查语言是否有限。有限语言意味着它被有限自动机接受。例如 L= {a^n b^m | n+m<100} 或 L={a^n b^n | n<50}。这些示例可能看起来是上下文无关语言，但实际上它们是有限的，因此被有限自动机接受。
- 检查语言给出的条件是否涉及单比较。如果它涉及不止一次比较，那么它既不是 Regular 也不是 Context-free。然后是上下文相关的语言。例如L= {a^n b^n c^n | n>1} 和 L={a^n b^n c^m | m>n} 都是存在不止一个比较的情况。在第一种情况下，它存在于语言的主体中，在第二个示例中，一个比较在主体中，另一个比较在语言条件中。
- 如果您了解 PDA 的设计知识，则很容易区分 PDA 和 DPDA。如果该语言包含一个明确的改变状态的点那么它就是 DPDA 否则就是 PDA。
- 如果上下文无关语言涉及相等条件，如 L={w.wR | {0,1}* } 或 L ={ a^nb^n| 的 w 元素n>1}，则PDA被空栈和最终状态接受，但如果条件不等，则需要检查栈是否为空。
- 尝试可视化堆栈并使用该堆栈尝试可视化是否可以进行给定的比较。一种语言要是 Context-free，就应该只用一个栈来比较。
- 如果语言复杂到足以猜测它是Regular 还是context-free，那么它必须是context-sensitive。没有任何方法可以直接判断一种语言是 R.E 还是上下文相关的，因此假设可以以集合生成器形式编写并且不是常规或上下文无关的每种语言都是上下文-敏感。
正如我之前所说，这些不是规定的规则或事实，而只是从这些语言的定义中得出的一些要点。为了快速猜出，就试着根据这些规则练习一些语言吧。