回答你的问题:
imagine a*b*是正则的,有没有证据证明它是正则的?
无需想象,无需表达a*b*
叫做regular e表达 http://en.wikipedia.org/wiki/Regular_expression(re),并且正则表达式仅适用于正则语言。如果一种语言不是正则语言,那么正则表达式也是不可能的,如果一种语言是正则语言,那么我们总是可以用某种正则表达式来表示它。
Yes, a*b*
代表一种常规语言。
语言描述: 任意数量a
后面跟着任意数量的b
(by 任何数字我的意思是零(包括空^
)或更多次)。一些示例字符串是:
{^, a, b, aab, abbb, aabbb, ...}
RE 的 DFAa*b*
将如下:
a- b-
|| ||
▼| ▼|
---►((Q0))---b---►((Q1))
In figure: `(())` means final state, so both `{Q0, Q1}` are final states.
您需要了解以下基本概念:
What is basically a regular language? And why an infinite language `a*b*` is regular whereas languages like `{ anbn | n > 0 }` are not regular!!
如果一种语言(一组)在处理该语言的字符串时只需要在任何时间保存有界(有限)量的信息,则该语言(集合)被称为常规语言。
那么,什么是“有界”信息?
例如:考虑风扇“开”/“关”开关。通过查看风扇开关我们可以得知风扇是否处于工作状态on
or off
状态(这是有界或有限的信息)。但我们无法判断风扇已切换“多少次”on
or off
在过去! (为了记住这一点,我们需要一种机制来存储“无限”数量的信息来计数——“多少次”,例如我们的汽车/自行车中使用的仪表)。
The language { anbn | n > 0 } is not a regular language because here n
is unbounded(it can be infinitely large). To verify strings in the language anbn, we need to memorize how many a
symbols there are and it requires an infinite memory storage to count because the number of a
symbols in the string can be infinitely large!
That means an automata is only capable of processing strings of the language anbn if it has infinite memory e.g PDA.
然而,a*b*
本质上当然是正则的,因为存在有界限制——即b
可能会在一些之后出现a
( and a
不能来之后b
)。这就是为什么这种语言的每个字符串都可以很容易地被我们拥有有限内存的自动机处理(或识别) - 并且有限自动机是一类内存有限的自动机。是的,在有限自动机中,我们的状态内存量是有限的。
(有限自动机中的记忆以状态的形式存在Q
根据自动机原理:任何自动机只能有有限的状态。因此,有限自动机的内存是有限的,这就是常规语言的自动机类被称为有限自动机的原因。你可以把有限自动机想象成一个没有内存的CPU,它有有限的寄存器来记住它的内部状态)
有限状态⇒有限内存⇒只有在处理字符串时需要在任何时刻存储有限内存的语言才能被处理⇒该语言称为常规语言
缺乏外部存储器是有限自动机的限制⇒或者我们可以说有限自动机定义的语言类别(称为常规语言)的限制。
你应该阅读其他答案“正则语言的有限性” https://stackoverflow.com/a/20818068/1673391学习常规语言的范围。
边注::
- language { anbn | n > 0 } is subset of
a*b*
- Also a language { anbn | 10>100 n > 0 } is regular, a large set but regular because
n
is bounded, hence finite automata and regular expression is possible for this language.
您还应该阅读:如何证明一种语言是正则语言? https://cs.stackexchange.com/questions/1331/how-to-prove-a-language-is-regular