regular-language - a*b* 是常规的吗？

Question

我知道 n > 0 的 anbn 不是抽引引理的规则，但我可以想象 a*b*是常规的，因为 a,b 不必是相同的长度。有没有证据证明它是正常的？

Answer 1

回答你的问题:

imagine a*b* to be regular, Is there a proof for it being regular or not?

无需想象，表情 a*b*被称为 regular expression (re) 和正则表达式仅适用于正则语言。如果一种语言不是正则的，那么正则表达式也是不可能的，如果一种语言是正则语言，那么我们总是可以用一些正则表达式来表示它。
是的， a*b*代表常规语言。
语言说明 :任意数量的 a 后跟任意数字 b (任何数字我的意思是零(包括 null ^ )或更多次)。一些示例字符串是:

{^, a, b, aab, abbb, aabbb, ...}

RE DFA a*b*将如下:

      a-            b-
      ||            ||
      ▼|            ▼|
---►((Q0))---b---►((Q1))

In figure: `(())` means final state, so both `{Q0, Q1}` are final states.

您需要了解以下基本概念:
什么是基本的常规语言？以及为什么无限语言 `a*b*` 是规则的，而像 `{ anbn | n > 0 }` 不规则!!
如果一种语言(一组)​​在处理该语言的字符串时只需要有限(有限)量的信息来保持存储在任何时间实例，则称为常规语言。
那么，什么是“有界”信息？
例如:考虑一个风扇“开”/“关”开关。通过查看风扇开关可以判断风扇是否在 on或 off状态(这是有界或有限的信息)。但是我们无法判断风扇已切换到“多少次” on或 off在过去! (为了记住这一点，我们需要一种机制来存储“无限”数量的信息来计算——“多少次”，例如我们的汽车/自行车中使用的仪表)。
语言 { anbn | n > 0 } 是 不是 常规语言，因为这里 n是无界的(可以无限大)。要验证 anbn 语言中的字符串，我们需要记住多少 a 有符号，它需要无限的内存存储来计数，因为 的数量a 字符串中的符号可以无限大!
这意味着自动机只有在具有无限内存(例如 PDA)的情况下才能处理语言 anbn 的字符串。
而， a*b*本质上当然是规则的，因为存在有界限制—— b 可能会在一些之后出现 a (和 a 不能跟在 b 之后)。这就是为什么这种语言的每个字符串都可以被我们拥有有限内存的自动机轻松处理(或识别)的原因 - 和 有限自动机是一类内存有限的自动机。是的，在有限自动机中，我们在状态方面的内存量是有限的。
(有限自动机中的内存以状态 Q 的形式存在，并且根据自动机原理:任何自动机只能具有有限状态。因此有限自动机具有有限内存，这就是将常规语言的自动机类称为有限的原因自动机。你可以把有限自动机想象成一个没有内存的 CPU，它有有限的寄存器来记住它的内部状态)
有限状态⇒有限内存⇒只有在处理字符串时需要在任何时间存储有限内存的语言才能被处理⇒该语言称为正则语言
没有外部存储器是有限自动机的限制⇒或者我们可以说有限自动机的限制定义了称为正则语言的语言类。
您应该阅读其他答案 "finiteness of regular language"学习正规语言的范围。
旁注: :

语言 { anbn | n > 0 } 是 a*b* 的子集

也是一种语言 { anbn | 10>100 n > 0 } 是规则的，一个很大的集合但是规则，因为 n是有界的，因此这种语言可以使用有限自动机和正则表达式。

您还应该阅读: How to prove a language is regular?