我正在为考试准备无上下文语法。我不明白为什么语言
{ a^n b^n | n>=0}
是上下文无关的,但不是常规的。为什么不规律?我们什么时候可以说表达式不规则?
谢谢
我正在为考试准备无上下文语法。我不明白为什么语言
{ a^n b^n | n>=0}
是上下文无关的,但不是常规的。为什么不规律?我们什么时候可以说表达式不规则?
谢谢
就像之前的答案中所说的那样,它的上下文无关,因为你可以用上下文无关的语法来表达它。
例如:S -> aSb | ε
它不是正则的,因为你不能用有限状态机或正则表达式来表达它。您应该能够计算 As 的数量并检查 B 的数量是否匹配。这不能用有限状态来完成,因为n可以是任何东西
标准方法是使用Pumping Lemma
好吧,您可以说它是上下文无关的,因为您可以使用上下文无关语法来表达它。然而,它不是正则的,因为正则表达式(和有限自动机)不能表示该语言。