正闭包
有关正则表达式的一元运算
正闭包是广泛应用于计算机科学领域中编译领域中有关正则表达式的一元运算。正闭包是由克林闭包衍生出的概念,因而它属于正则表达式的扩展运算。
提出背景
20世纪50年代,美国数学家斯蒂芬·科尔·克莱尼提出了正则表达式的三类基本运算:并、连接、克林闭包(又称星闭包,Kleene星号)。此后学界发现很多时候需要描述一个语言连接1次或以上得到的集合,因此由克林闭包的概念衍生出了正闭包的概念。
定义
对于语言L,L的正闭包定义为:
性质
1、幂等性:
2、结合性:正闭包具有左结合性。
3、优先级:正闭包和克林闭包一样在正则表达式运算中具有最高优先级。
4、由克林闭包推出正闭包:
5、由正闭包推出克林闭包:
实例
例:由a和b组成且不含有三个连续的b的字符串的正则表达式(All strings of a's and b's that contain no three consecutive b's)。
答案:
题目来源:《编译原理与实践》(英文版)第2章课后题2.1.f题
解析:不含有三个连续的b意味着除了{b}和{bb}这两种不含有a的情况外,每至多出现2个连续的b后必须出现至少1个a,因此构造出,但这样写忽略了以b结尾的情况,因此要在后面连接。这样再并上b和bb,得到正解。
参考资料
最新修订时间:2024-05-21 11:46
目录
概述
提出背景
定义
性质
实例
参考资料