常规语言与非常规语言

Question

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

Answer 1

正则语言在字母A上递归定义,如下所示:

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

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

它遵循所有这些步骤,除了6,A上的每个有限的字符串集都是规则的.当我们考虑无限集时,所有有趣的东西都会发生.

正则表达式只是表示常规语言的"编程语言".他们这样工作.我将使用"regex"作为正则表达式的缩写.

1. 正则表达式\ NULL表示空集.
2. 正则表达式\ EPS代表{\ eps}.
3. 正则表达式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的二进制表示(字母{0,1})的集合S_k,而不是N == 0 mod k.你可以选择你喜欢的任何正整数k.

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

任何集合S_k的正则表达式,如你所愿选择k,如上所述是非常复杂的,但识别它的DFA非常简单.Kleene的定理让您继续使用最好的工具.

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

同一个想法的另一个陈述:如果你声称你有一个NFA状态的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},以及类似的无限.

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

Answer 2

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

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

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

人们可以使用泵引理证明某些语言（字符串集）不能用正则表达式来表达。例如，如果语言中的' 的个数与' 的个数{ab,aabb,aaabbb,...}一样多，则无法使用正则表达式来表达。ab

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