8

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

4

2 回答 2

13

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

  1. 空集 \null 是常规的。
  2. 集合 { \eps } 是常规的，其中 \eps 是空字符串。
  3. 集合 { a } 对所有 a \in A 都是正则的
  4. 如果 X 和 Y 是正则的，则集合 { xy | x \in X, y \in Y } 也是正则的。
  5. 如果 X 和 Y 是正则的，则 X \union Y 也是正则的。
  6. 如果 X 是正则的，那么 { x^n | x \in X 和 n >= 0 }

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

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

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

  1. 正则表达式 \NULL 代表空集。
  2. 正则表达式 \EPS 代表 { \eps }。
  3. 正则表达式a代表集合 { a }。请注意，粗体a表示正则表达式，而不是它所代表的字符 a。
  4. 如果正则表达式x代表语言 X，y代表 Y，那么正则表达式xy代表语言 { xy | x \in X, y \in Y }。
  5. 如果正则表达式x代表语言 X，y代表 Y，那么正则表达式x|y代表语言 X \union Y。
  6. 如果正则表达式x代表语言 X，则正则表达式x*代表语言 { x^n | x \in X, n >= 0 }。

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

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

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

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

任何集合 S_k 的正则表达式，如你所愿选择 k，上面描述的非常复杂，但识别它的 DFA 非常简单。Kleene's Theorem 让您继续使用最好的工具。

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

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

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

非常规语言的例子包括前面提到的 { a^nb^n | n >= 0 } 以及需要各种“平衡”的类似语言：{ a^nb^m | n > m }、{ a^nba^n } 和无数类似的。

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

于 2013-09-10T06:02:36.053 回答
4

如果可以将表达式分解为四个基本语言概念，则该表达式是正则表达式：

  • 单个字符。例如a, b,c
  • 两个正则表达式之间的连接。例如ab，abc
  • 两个正则表达式之间的析取。例如a|b
  • 克莱恩星：例如(ab)*

正则表达式的其他方面只是语法糖。例如(ab)+是 的缩写(ab)(ab)*和[A-F]是 的缩写A|B|C|D|E|F。

可以使用Pumping lemma证明某些语言（字符串集）不能用正则表达式表达。例如，剩下的' 和 '{ab,aabb,aaabbb,...}一样多的语言不能使用正则表达式来表示。ab

Chomsky定义了一个关于如何识别这些语言的层次结构（例如使用上下文无关语法（CFG）、上下文敏感语法（CSG）、图灵机和Oracle 机器） 。

于 2013-09-10T04:40:09.533 回答