是* b *常规？
我知道n> 0对于n> 0是不规则的泵浦引理，但我会想象a*b*是规则的，因为a，b不必是相同的长度。 有没有证据certificate它是正常的？
回答你的问题：
想象a * b *是正常的，是否有证据表明它是正常的？
不需要想象，expression式a*b*被称为r egular e xpression （re），正则expression式只能用于正则语言。 如果一个语言不是一个正则expression式，那么正则expression式也是不可能的，如果一种语言是正则语言，那么我们总是可以用正则expression式来表示它。
是的， a*b*表示正规语言。
语言描述 ：任何数字a后跟任意数字b （ 任意数字，我的意思是零（包括null ^ ）或更多次数）。 一些示例string是：
{^, a, b, aab, abbb, aabbb, ...}
RE a*b* DFA将如下所示：
a- b- || || ▼| ▼| ---►((Q0))---b---►((Q1)) In figure: `(())` means final state, so both `{Q0, Q1}` are final states.
您需要了解以下基本概念：
什么基本上是一个正规的语言？ 为什么一个无限的语言`a * b *`是规则的，而像`{a n b n | n> 0}`不正常！
一个语言（一组）被称为正规语言，如果它只需要有限的（有限的）量的信息，以便在处理该语言的string的任何时刻保持存储。
那么，“有界”的信息是什么？
例如：考虑风扇“开”/“关”开关。 通过查看风扇开关，我们可以说风扇是处于on还是off状态（这是有限的或有限的信息）。 但是我们不能说“过去有多less次风扇被开关了！ （记住，它需要一个机制来存储“无限量”的信息来计算 – “多less次”，例如某种仪表在我们的汽车/自行车中使用的）。
语言{a n b n | n> 0} 不是一个正规的语言，因为这里n是无界的（可以是无穷大的）。 为了validation语言a n b n中的string，我们需要记住有多lessa符号来到，并且由于string中符号的数量可能无限大，因此需要无限存储器来进行计数。
这意味着，如果自动机具有无限的内存，例如PDA，则自动机只能处理语言的string。
鉴于a*b*的性质当然是规则的，因为存在有限的限制 – b可能会在某个a之后a （而a不能在b之后出现）。 这就是为什么这种语言的每个string都可以通过一个有限内存的自动机来处理（或识别） – 而有限自动机就是一类内存有限的自动机。 是的，在有穷自动机中，在状态方面我们的存储量是有限的。
（ 有限自动机中的记忆以状态Q的forms出现，并根据自动机原理：任何自动机只能有限状态，因此有限自动机具有有限的记忆，这就是正规语言自动机类被称为有限自动机的原因。可以认为像CPU这样的有限自动机没有记忆，有记忆的有限的记忆它的内部状态 ）
有限状态⇒有限存储器⇒在处理string的过程中，只有语言才是有限存储器需要存储的过程⇒这种语言称为正则语言
缺less外部记忆是有限自动化的限制⇒或者我们可以说限制有限自动机定义的类语言称为规则语言。
你应该阅读其他答案“正规语言的有限性”来学习正规语言的范围。
旁注 ：
- 语言{a n b n | n> 0}是
a*b* - 还有一种语言{a n b n | 10 > 100 n> 0}是规则的，一个大的集合，但是规则的，因为
n是有界的，因此有限自动机和正则expression式是可能的这种语言。
你还应该阅读： 如何certificate一种语言是正常的？
certificate是： ((a*)(b*))是一个格式良好的正则expression式，因此与正则语言匹配。 a*b*是相同expression式的句法缩短。
另一个certificate：正则语言是closures连接的。 a *是一种常规语言。 b *是常规语言，因此它们的连接a * b *也是正则expression式。
你可以为它build立一个自动装置：
0 ->(a) 1 0 ->(b) 2 1 ->(a) 1 1 ->(b) 2 2 ->(b) 2 2 ->(a) 3 3 ->(a,b) 3
只有3个不是接受状态，并且certificate语言是a * b *。
为了certificate一种语言是正规的，只要显示下面的内容就足够了：
1）有一些DFA可以识别它。 在这种情况下，DFA是微不足道的。
2）语言可以expression为一个正则expression式，如另一个答案中提到的。 a*b*是识别这种语言的正则expression式。
