finite-automata - contex free 不规则是什么意思

Question

我正在为考试准备无上下文语法。我不明白为什么语言

{ a^n b^n | n>=0}

是上下文无关的，但不是常规的。为什么不规律？我们什么时候可以说表达式不规则？

谢谢

Answer 1

如果表达式不能（完全）被正则表达式或（等效地）有限状态机匹配，则表达式不是正则表达式。另请参阅上下文无关语言和常规语言。

Answer 2

就像之前的答案中所说的那样，它的上下文无关，因为你可以用上下文无关的语法来表达它。

例如：S -> aSb | ε

它不是正则的，因为你不能用有限状态机或正则表达式来表达它。您应该能够计算 As 的数量并检查 B 的数量是否匹配。这不能用有限状态来完成，因为n可以是任何东西

Answer 3

标准方法是使用Pumping Lemma

Answer 4

好吧，您可以说它是上下文无关的，因为您可以使用上下文无关语法来表达它。然而，它不是正则的，因为正则表达式（和有限自动机）不能表示该语言。