1

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

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

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

谢谢

4

4 回答 4

3

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

于 2010-01-13T07:17:33.780 回答
3

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

例如:S -> aSb | ε

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

于 2010-01-13T07:42:27.087 回答
2

标准方法是使用Pumping Lemma

于 2010-01-20T22:12:43.797 回答
1

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

于 2010-01-13T07:17:49.893 回答