是*b*常规吗？

Question

我知道^ñ b ^ñ对于n> 0不是由泵引理经常但我想a*b*,以定期,因为两个A,B不必是相同的长度.有证据证明它是正常的吗？

Answer 1

回答你的问题:

想象一下*b*是常规的,是否有正常的证明？

无需想象,表达 a*b*被称为[R egular Ë上的表达(RE)和正则表达式可能只对正规语言.如果一种语言不是常规语言,那么正则表达式也是不可能的,如果一种语言是常规语言,那么我们总是可以通过一些正则表达式来表示它.

是的,a*b*代表一种常规语言.

语言描述:任意数量的a后跟任意数字b(任何数字我的意思是零(包括空^)或更多次).一些示例字符串是:

{^, 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*`是常规语言,而像`{a <sup>n</sup> b <sup>n</sup> | n> 0}`不规律!

语言(集合)被称为常规语言,如果它只需要有限(有限)量的信息来在处理语言字符串时保持存储在任何时间.

那么,什么是"有界"信息？
例如:考虑一个风扇'开'/'关'开关.通过查看风扇开关,我们可以说风扇是否处于on或off状态(这是有界的或有限的信息).但是我们不能说过去一次风扇的开启和关闭"多少次"!(记住,它需要一种机制来存储'无限'的信息量 - '多少次',例如某种仪表用于我们的汽车/自行车).

语言{a ⁿ b ⁿ | n> 0} 不是常规语言,因为这里n是无界的(可以是无穷大).为了验证字符串语言^ň b ^ñ,我们需要记住的是多少a符号已经来了,它需要无限大的存储器来算,因为数a符号字符串可以是无限大!

这意味着,一个自动机仅能够处理的语言串的^Ñ b ^Ñ如果它具有无穷的存储器例如PDA.

然而,a*b*由于存在有限的限制 - 这b可能是在一些之后a(并且a不可能在之后b),因此当然是有规律的.这就是为什么这种语言的每一个字符串都可以被我们拥有有限内存的自动机轻松处理(或识别)的原因 - 而 有限自动机是一类内存有限的自动机.是的,在有限自动机中,我们在状态方面具有有限的内存量.

(有限自动机中的记忆以状态的形式存在,Q并且根据自动机原理:任何自动机都只能有有限状态.因此有限自动机具有有限的记忆,这就是常规语言的自动机类被称为有限自动机的原因.你可以认为像CPU没有内存的有限自动机,有有限的寄存器来记住它的内部状态)

有限状态⇒有限存储器⇒在处理字符串时,只有语言可以处理有限存储器在任何时刻需要存储的处理⇒该语言称为常规语言

没有外部记忆是有限自动化的限制⇒或者我们可以说限制有限自动机定义的语言类称为常规语言.

你应该阅读其他答案"常规语言的有限性"来学习常规语言的范围.

旁注:

• 语言{a ⁿ b ⁿ | n> 0}是.的子集a*b*
• 也是一种语言{a ⁿ b ⁿ | 10 ^{> 100} n> 0}是规则的,一个大的集合但是规则因为n是有界的,因此有限的自动机和正则表达式对于这种语言是可能的.

您还应该阅读:如何证明一种语言是正规的？