我知道对于n> 0的anbn不是通过泵浦引理的常规但我想象a*b*
是规则的,因为a,b不必是相同的长度。有证据证明它是正常的吗?
回答你的问题:
想象一下* b *是常规的,是否有正常的证明?
无需想象,表达式a*b*
称为regular expression(re),正则表达式仅适用于常规语言。如果一种语言不是常规语言,那么正则表达式也是不可能的,如果一种语言是常规语言,那么我们总是可以用一些正则表达式来表示它。
是的,a*b*
代表一种常规语言。
语言描述:任意数量的a
后跟任意数量的b
(任何数字我的意思是零(包括null ^
)或更多次)。一些示例字符串是:
{^, 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.
您需要了解以下基本概念:
语言(集合)被称为常规语言,如果它只需要有限(有限)量的信息来在处理语言字符串时保持存储在任何时间。
那么,什么是“有界”信息?
例如:考虑一个风扇'开'/'关'开关。通过查看风扇开关我们可以说风扇是在on
还是off
状态(这是有限的或有限的信息)。但是我们不能说过去一次风扇的开启和关闭“多少次”! (记住,它需要一种机制来存储'无限'信息量 - '多少次',例如某种仪表在我们的汽车/自行车中使用的数量)。
语言{anbn | n> 0}不是常规语言,因为这里n
是无界的(可以是无穷大)。为了验证语言anbn中的字符串,我们需要记住已经出现了多少个a
符号,并且需要无限的内存存储来计算,因为字符串中的a
符号数量可能是无穷大的!
这意味着,如果自动机具有无限的内存,例如PDA,则它只能处理语言字符串anbn。
然而,a*b*
的性质当然是正常的,因为有限制和冲刺; b
可能来自一些a
(并且a
不能来自b
)。这就是为什么这种语言的每一个字符串都可以被我们拥有有限内存的自动机轻松处理(或识别)的原因 - 而有限自动机是一类内存有限的自动机。是的,在有限自动机中,我们在状态方面具有有限的内存量。
(有限自动机中的记忆以状态Q
的形式存在并且根据自动机主体:任何自动机都只能有有限状态。因此有限自动机具有有限的记忆,这就是常规语言的自动机类被称为有限自动机的原因。可以认为像CPU没有内存的有限自动机,有有限的寄存器来记住它的内部状态)
有限状态⇒有限存储器⇒在处理字符串时,只有语言可以处理有限存储器在任何时刻需要存储的处理⇒该语言称为常规语言
没有外部记忆是有限自动机的限制⇒或者我们可以说限制有限自动机定义的语言类称为常规语言。
你应该阅读其他答案"finiteness of regular language"来学习常规语言的范围。
边注::
a*b*
的子集n
是有界的,因此有限的自动机和正则表达式对于这种语言是可能的。证据是:((a*)(b*))
是一个结构良好的正则表达式,因此匹配常规语言。 a*b*
是同一表达式的句法缩写。
另一个证明:常规语言不能连接。 a *是一种常规语言。 b *是常规语言,因此它们的连接a * b *也是正则表达式。
您可以为它构建一个自动机:
0 ->(a) 1
0 ->(b) 2
1 ->(a) 1
1 ->(b) 2
2 ->(b) 2
2 ->(a) 3
3 ->(a,b) 3
其中只有3个不是接受状态,并证明该语言是* b *。
要证明某种语言是正规的,只需显示:
1)存在一些识别它的DFA。在这种情况下,DFA是微不足道的。
2)语言可以表达为正则表达式,如另一个答案中所述。 a*b*
是识别这种语言的正则表达式。
常规语言是可以用正则表达式或确定性或非确定性有限自动机或状态机表达的语言。语言是一组字符串,由指定字母或符号集中的字符组成。常规语言是所有字符串集的子集。
闭包属性是一种声明,当语言的某些操作应用于类中的语言(例如,常规语言)时,会产生同样在该类中的结果。
这个RE显示了接受多个(a)(如果有的话)之前的语言类型(b)
表示不包含任何子字符串的语言(ba)