正则语言与非正则语言

Question

在正规语言的正式定义中，有没有人能帮我区分一下正规语言(即那些可以用正规表达式描述的)和其他非正规语言？此外，你能提供一些两边的例子吗？

Answer 1

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

和空集\

1. 是正则的。
2. 集合{\ is }是正则的，其中\ is是空字符串。
4. 如果X和Y是正则的，则集合{a}是正则的。如果X和Y是正则的，则集合{ xy |x \in X，y \in Y}也是正则的。如果X和Y是正则的，则X\

Y也是正则的。H210 H111如果X是正则的，那么{ x^n |x \in X >= n}G213也是正则的

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

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

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

1. 正则表达式\

代表空集。

1. 正则表达式\EPS代表{\ep }。
2. regex a代表集合{a}。注意，的粗体表示正则表达式而不是字符a，它代表正则表达式x代表语言X，y代表语言Y，那么正则表达式 xy 代表语言{xy|x \in X，y \in Y}。如果正则表达式E134<>x<代码>E235代表语言X，<代码>E136>y<代码>E237代表Y，则regex xy代表语言{xy|x\in X，y\in Y}。则正则表达式x|y代表语言X\Y。
   1. 如果正则表达式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的正则表达式都非常复杂，但识别它的DFA却非常简单。Kleene定理允许您使用最好的工具进行操作。

有限自动机实际上拥有有限的内存，所以你会期望--你也是对的--具有某种无限结构的语言不会是正规的。最简单的这种语言可能是{ a^n b^n |n >= 0 }。任何有限自动机(因此regex或NFA)一定不能“存储”在查看a时记录的n值(如果n足够大)。因此，它在查找输入中后面出现的相同数量的b时肯定会失败。

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

Pumping引理利用了这一事实。它提供了一种严格的数学证明方法(通过引理的矛盾)来证明语言不是正则的。每一个优秀的计算机科学专业的学生都会学习以PL所要求的方式“向上(或向下)”来证明集合是非规则的。

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

非正则语言可以进一步细分为复杂度越来越高的集合:上下文无关语言、上下文敏感语言、递归集、递归可枚举集和不可判定集。然而，这些仅仅是更复杂的字符串集的无限层次结构的开始。这个无限的集合是无限复杂的！尽情享受吧。

Answer 2

如果一个表达式可以分解成四个基本的语言概念，那么它就是正则表达式：

• 单个字符。例如，两个正则表达式之间的c
• a、a、b连接。例如，abc
• a析取两个正则表达式之间的ab。例如a|b
• a Kleene-star:例如(ab)*

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

可以使用证明某些语言(字符串集)不能用正则表达式表示。例如，剩余的a和b一样多的语言{ab,aabb,aaabbb,...}不能使用正则表达式来表示。

乔姆斯基定义了关于如何识别这些语言的hierarchy (例如，使用上下文无关语法、上下文敏感语法、图灵机和甲骨文机器)。