regex - 正则语言与非正则语言

Question

关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。












想改善这个问题吗？更新问题，使其成为 on-topic对于堆栈溢出。

7年前关闭。




Improve this question




任何人都可以帮助我区分正则语言(即可以用正则表达式描述的语言)和其他在正则语言的正式定义方面不规则的语言吗？此外，您能否提供一些双方的例子？

Answer 1

常规语言在字母 A 上递归定义如下:

空集\null 是规则的。

集合 {\eps } 是常规的，其中\eps 是空字符串。

集合 { a } 对所有 a\in A

都是正则的

如果 X 和 Y 是正则的，则集合 { xy | x\in X, y\in Y } 也是规则的。

如果 X 和 Y 是正则的，那么 X\union Y 也是正则的。

如果 X 是正则的，那么 { x^n | 也是正则的x\in X 和 n >= 0 }

6中，x^n的定义是x与自身连接n次，x^0 =\eps。

从除 6 之外的所有这些步骤可以得出，A 上的每个有限字符串集都是正则的。当我们考虑无限集时，所有有趣的事情都会发生。

正则表达式只是一种用于表示正则语言的“编程语言”。他们是这样工作的。我将使用“regex”作为正则表达式的缩写。

正则表达式\NULL 代表空集。

正则表达式\EPS 代表 {\eps }。

正则表达式 代表集合 { a }。注意粗体 意味着一个正则表达式而不是它所代表的字符 a。

如果正则表达式 x 代表语言 X 和 y 代表 Y，然后是正则表达式 xy 代表语言 { xy | x\in X, y\in Y }。

如果正则表达式 x 代表语言 X 和 y 代表 Y，然后是正则表达式 x|y 代表语言 X\union Y。

如果正则表达式 x 代表语言 X，然后是正则表达式 x* 代表语言 { x^n | x\in X, n >= 0 }。

定义直接暗示了每个正则表达式都描述了一种正则语言。反其道而行之并不难证明每种常规语言都必须有相应的正则表达式。

所以你要求的正则语言的例子都是一些正则表达式所代表的。示例: ab* 是所有以 a 开头的字符串的语言，后跟任意数量的 b 等等。

有一些非常酷的语言看起来太复杂而不是常规的，但实际上是。我最喜欢的是所有数字 N 的二进制表示(字母 {0, 1})的集合 S_k，例如 N==0 mod k。您可以选择任何您喜欢的正整数 k。

由于 Kleene 有一个很棒的定理，它可以走得更远。它表明 Deterministic Finite Automata 可识别的语言- 简单的状态机 - 和非确定性有限自动机 - 在空字符串上具有转换并且允许在每个字符上进行多次转换的状态机 - 正是常规语言。它们都具有相同的表达能力。也就是说，如果你给我 {regex, DFA, NFA } 中的任何一个，我每次都可以转换为其他两个。

任何集合 S_k 的正则表达式，根据需要选择 k，如上所述非常复杂，但识别它的 DFA 非常简单。 Kleene 定理可让您继续使用最佳工具。

有限自动机有效地具有有限的内存，所以你会期望——你是对的——具有某种无限结构的语言不会是正则的。最简单的这种语言可能是 { a^n b^n | n >= 0 }。那是 a 的所有字符串后跟相同数量的 b 的集合。如果 n 足够大，则任何有限自动机(因此正则表达式或 NFA)在查看 a 时都必须无法“存储”记录的 n 值。因此，它在寻找输入中稍后出现的相同数量的 b 时必须失败。

同样想法的另一个陈述:如果你声称你有 N 个状态的 DFA，它将识别 { a^n b^n | n >= 0 }，我会给你字符串 { a^k b^k | k > N } 它将不得不失败，因为它必须“循环”，即重复至少一种状态。在这一点上，它已经忘记了到目前为止它已经阅读了多少。对于这些长字符串中的一些，它注定会得到错误的答案。

Pumping Lemma 利用了这一事实。它提供了一种数学上严格的证明(与引理矛盾)语言不是正则的方法。每个优秀的计算机科学专业的学生都学会以 PL 所需的方式“提高(或降低)”以证明集合是非常规的。

非常规语言的例子包括前面提到的 { a^n b^n | n >= 0 } 以及需要各种“平衡”的类似语言:{ a^n b^m | n > m }, { a^n b a^n }，以及无数相似的。

非常规语言可以进一步分割为越来越复杂的集合:上下文无关语言、上下文敏感语言、递归集、递归可枚举集和不可判定集。然而，这些只是越来越复杂的字符串集的无限层次结构的开始。这个无限集是无限复杂的!好好享受。