7

我知道 n > 0 的n b n根据抽水引理不规则，但我想a*b*是规则的，因为 a,b 不必是相同的长度。有没有证明它是正常的或不正常的？

4

4 回答 4

19

回答你的问题：

想象a*b*是规则的，是否有证据证明它是规则的？

不用想象，表达式 被a*b*称为正则表达式（ re），而正则表达式只有正则语言才有可能。如果一种语言不是正则的，那么正则表达式也是不可能的，如果一种语言是正则语言，那么我们总是可以用一些正则表达式来表示它。

是的，a*b*代表一种常规语言。

语言描述：任意数量的a后跟任意数量的b（任何数量我的意思是零（包括 null ^）或更多次）。一些示例字符串是：

{^, 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.

您需要了解以下基本概念：

什么是基本的常规语言？以及为什么无限语言 `a*b*` 是常规语言，而像 `{ a n b n | n > 0 }` 不规则！！

一种语言（一组）​​被称为常规语言，如果它在处理语言字符串时只需要有限（有限）数量的信息来保持存储在任何时间实例。

那么，什么是“有界”信息？
例如：考虑一个风扇“开”/“关”开关。通过查看风扇开关，我们可以判断风扇是否处于onoroff状态（这是有界或有限信息）。on但我们无法判断一个风扇已经切换到或off过去“多少次” ！（为了记住这一点，我们需要一种机制来存储“无限”数量的信息以进行计数——“多少次”，例如我们的汽车/自行车中使用的仪表）。

语言 { a n b n | n > 0 }不是常规语言，因为这里n是无界的（它可以无限大）。为了验证语言 a n b n中的字符串，我们需要记住有多少a符号，并且需要无限的内存来计算，因为a字符串中的符号数量可以无限大！

这意味着自动机只有在具有无限内存（例如 PDA ）的情况下才能处理语言 a n b n的字符串。

然而，a*b*当然，就其性质而言，它是有规律的，因为存在有限的限制——b可能会出现在某些a（并且a不能出现在b）之后。这就是为什么这种语言的每个字符串都可以很容易地被我们拥有有限内存的自动机处理（或识别）——而 有限自动机是一类内存有限的自动机。是的，在有限自动机中，我们在状态方面的内存量是有限的。

（有限自动机中的内存以状态的形式存在，Q并且根据自动机原理：任何自动机只能有有限状态。因此，有限自动机的内存是有限的，这就是常规语言的自动机类被称为有限自动机的原因。你可以把有限自动机想象成一个没有内存的 CPU，它有有限的寄存器来记住它的内部状态）

有限状态⇒有限内存⇒在处理字符串时，只能处理需要在任何时间实例存储有限内存的语言⇒该语言称为常规语言

没有外部存储器是有限自动机的限制⇒ 或者我们可以说有限自动机定义的语言类称为常规语言的限制。

您应该阅读其他答案“常规语言的有限性”以了解常规语言的范围。

旁注：：

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

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

于 2013-05-24T08:30:52.790 回答
2

证明是：((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 不是接受状态，并证明语言是 a*b*。

于 2013-05-23T20:22:40.257 回答
0

为了证明一种语言是正则的，只要证明以下之一就足够了：

1）存在一些识别它的DFA。在这种情况下，DFA 是微不足道的。

2）语言可以表示为正则表达式，如另一个答案中所述。a*b*是识别这种语言的正则表达式。

于 2013-05-23T20:25:11.603 回答
0

正则语言是可以用正则表达式或确定性或非确定性有限自动机或状态机表示的语言。语言是一组字符串，由指定字母表中的字符或一组符号组成。正则语言是所有字符串集合的子集。

闭包属性是一种声明，当应用于类中的语言（例如，常规语言）时，对语言的特定操作会产生也在该类中的结果。

此 RE 显示..接受 (a) 的倍数（如果有）但在 (b) 之前的语言类型

表示不包含任何子字符串的语言 (ba)

于 2019-03-11T18:45:39.583 回答