计算理论 - 证明语言是正则的
我正在复习我的计算理论课程的一些笔记，我有点坚持显示以下陈述，我希望有人可以帮助我解释:)
让 A 成为一种常规语言。语言 B = {ab | a 存在于 A 中，b 不存在于 A*} 为什么 B 是常规语言？
有些观点对我来说是显而易见的。如果 b 只是一个常量字符串，那么这是微不足道的。由于我们知道 a 在 A 中，b 是一个字符串，因此常规语言在 union 下是封闭的，因此联合接受这两个字符串的语言显然是常规的。不过，我不确定 b 是否恒定。也许是这样，如果是这样，那么这并不是一个真正的问题。我很难理解它。谢谢！
I'm reviewing some notes for my course on Theory of Computation and I'm a little bit stuck on showing the following statement and I was hoping somebody could help me out with an explanation :)
Let A be a regular language. The language B = {ab | a exists in A and b does not exist in A*}
Why is B a regular language?
Some points are obvious to me. If b is simply a constant string, this is trivial. Since we know a is in A and b is a string, regular languages are closed under union, so unioning the language that accepts these two strings is obviously regular. I'm not sure that b is constant, however. Maybe it is, and if so, then this isn't really an issue. I'm having a hard time making sense of it. Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你可以通过构造来证明：给出一个识别B的正则表达式。正则语言的类在并集、串联、星号和补集下是封闭的。
You can prove by construction: Give a regular expression that recognizes B. The class of regular languages is closed under union, concatenation, star, and complement.
问题中的
a和b不是常量字符串而是任意字符串，B是字符串的语言，字符串开头在A，结尾在A现在，由于任何正则语言都可以通过正则表达式来识别，如果Ra是识别语言 A 的正则表达式，则Ra与“not Ra”正则表达式是识别语言B的正则表达式。由于B可以被正则表达式识别，所以它是正则语言。编辑：我最初错过了问题中 B 定义末尾 A 后面的星号。为了解决这个问题，请使正则表达式中识别
b的部分也包含星号。The
aandbin the question are not constant strings but any strings, and B is the language of strings with the beginning of the string in A and the end of the string not in A. Now, since any regular language can be recognised by a regular expression, ifRais the regular expression to recognise the language A, thenRaconcatenated with the “not Ra” regular expression is the regular expression to recognise the language B. Since B can be recognised by a regular expression, it's a regular language.Edit: I initially missed the star after the A at the end of the definition of B in the question. To account for it, make the part of the regular expression that recognises
balso include the star.B 是常规语言，因为它是当输入“b”出现时结束的语言。
我们可以将给定语言 B 的正则表达式写为 a*b
B is a regular language because it is language that ends when a input "b" appear.
we can write a regular expression for the given language B as a*b