上下文无关而不是常规是什么意思
我正在为考试准备上下文自由语法。我无法理解为什么该语言
{ a^n b^n | n>=0}
是上下文无关的但不是常规的。为什么不规律呢？ 什么时候我们可以说一个表达式不是正则表达式？
谢谢
I am preparing contex free grammar for an exam. I couldn't understand why the language
{ a^n b^n | n>=0}
is context free but not regular. Why is it not regular?
When can we say that an expression is not regular?
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果一个表达式不能被 正则表达式（完全）匹配，则该表达式不是正则表达式，或者（等价地） ) 一个有限状态机。另请参阅上下文无关语言和常规语言。
An expression is not regular if it cannot be matched (exactly) by a regular expression or (equivalently) a finite state machine. See also context free language and regular language.
就像之前的答案中所说的那样，它是上下文无关的，因为你可以用上下文无关的语法来表达它。
例如： S ->砷化镓 | ε
它不是正则的，因为你不能用有限状态机或正则表达式来表达它。您应该能够计算 A 的数量并检查 B 的数量是否匹配。这不能用有限状态来完成，因为 n 可以是任何东西
Like said in previous answers, its context free because you can express it with context free grammar.
For example: S -> aSb | ε
Its not regular because you cannot express it with finite state machine nor regular expressions. You should be able to count the number of As and check that number of Bs match. This cannot be done with finite states as n could be anything
标准方法是使用泵送引理
The standard approach is to use the Pumping Lemma
好吧，你可以说它是上下文无关的，因为你可以使用上下文无关语法来表达它。然而它不是正则的，因为正则表达式（和有限自动机）不能表示该语言。
Well you can say it is context free because you can express it using a Context-Free Grammar. It is not regular however because a regular expression (and finite automata) can not represent that language.