我们都知道这(a + b)*是一种只包含符号a和的常规语言b。但是(a + b)*是一个无限长的字符串，它是有规律的，因为我们可以构建一个有限自动机，所以它应该是有限的。
谁能解释一下？
问问题
3203 次
5 回答
8
任何正则语言都可以构造有限自动机，而正则语言可以是有限集或无限集。当然，有无限集不是规则集。检查下面的维恩图：
注：
1. 每个有限集都是正则集。
2. 无限集的任何 dfa 将始终包含循环（或者无限集不可能没有循环的 dfa）。
3. 每一种非常规语言都是一个无限集。
有限自动机中的“有限”一词意味着常规语言类的自动机中存在“有限量的内存”，因此在处理时的任何时间实例都只能存储“有限”（或说有界）数量的信息一串语言。
在有限自动机中，内存仅以状态的形式存在（而在另一类自动机如 Pda 中，图灵机的外部内存用于存储无限信息）。您可以将有限自动机视为没有显式内存的 CPU；只能将最近的结果存储在其寄存器中。
因此，我们可以将“常规语言”定义为——一类语言，在处理语言字符串时，在任何时间实例中只需要存储有界（有限）信息。
进一步阅读（无限语言）：
- 什么是常规语言：什么是基本的常规语言？为什么
a*b*是常规的？但是语言不是常规语言{ anbn | n > 0 } - 要了解状态如何用作内存元素，请阅读此答案：如何为 DFA 编写正则表达式
- 有限和无限正则语言的自动化之间的区别：确保：只为无限正则语言抽取引理？
于 2013-12-28T18:45:47.037 回答
4
语言中的每个单词(a+b)都是有限长度的。就像有无限多个整数一样，但每个整数都是有限的。
是的，语言本身就是一个无限集合。大多数语言都是。但是有限自动机（注意：自动机是复数）对他们来说工作得很好，只要每个单词的长度都是有限的。
顺便说一句：这类问题可能应该去 cs.stackexchange.com。
于 2013-12-27T16:24:55.370 回答
2
但是
(a + b)*是无限长的字符串
不，(a + b)*是表达有限字符串的无限集合（语言）的有限方式。
于 2013-12-30T20:05:09.083 回答
1
1.正则表达式描述了某种语言生成的字符串。应用该正则表达式可为您提供该语言可以描述的所有字符串。
2.当您将该正则表达式转换为有限自动机（具有有限状态的自动机）时，这意味着也可以通过在该自动机上从状态到状态的遍历来生成相同的字符串。现在，直观地说，这里的每个状态都代表一组属于该语言的字符串。它说，在“吸收”了一些输入之后，字符串现在处于状态 X。
例子：
如果您希望正则表达式接受偶数为0的字符串，那么您将拥有一个状态（组），表示到目前为止在输入中观察到偶数0 。奇数的另一个状态（组）->此状态将是您在 FA 中的不接受状态。
如此处所示，您只需要 2 个（有限）状态来生成无限数量的字符串，因为我们做了奇数和偶数的分组。
这就是为什么它是常规的。
于 2013-12-27T16:37:32.817 回答
0
它只是意味着存在指定语言的有限正则表达式，并且与从表达式生成的字符串无关。对于许多正则语言，我们可以生成无限数量的字符串，这些字符串遵循该语言，但该语言是正则的，以证明我们需要一个必须是有限的正则表达式。因此，这里的表达式 (a+b)* 是表达 0-n 个 a 或 b 或它们的组合的有限方式，但 n 可以采用任何值，从而导致无穷大。的字符串。
于 2016-04-06T03:14:17.100 回答