上下文无关语言的各种属性(CFL)
上下文无关语言(CFL) 是由上下文无关语法或类型 2 语法(根据乔姆斯基分类)生成并被下推自动机接受的语言。
上下文无关语言的一些非常重要的属性是:
正则性上下文无关语言是非正则 PDA 语言。
闭包属性 : 上下文无关语言在某种特定的操作下是封闭的，封闭意味着在对上下文无关语言进行该操作后，结果语言也将是上下文无关语言。一些这样操作是:
- 联合行动
- 串联
- 克莱尼关闭
- 反转操作
- 同形
- 逆同态
- 代替
- 初始化或前缀操作
- 正则语言商
- 循环作业
- 与常规语言的结合
- 与常规语言的交集
- 与常规语言的区别
上下文无关语言在某种特定的操作下不是封闭的，非封闭意味着在对上下文无关语言执行该操作后，结果语言不再是上下文无关语言。
一些这样操作是:
- 交集
- 补充
- 子集
- 超集
- 无限联盟
- 差、对称差(异或、与非、或非或任何其他可简化为求交和求补的运算
决策属性 :
- 成员资格测试:可判定。
- 空虚测试:可判定
- 有限性测试:可判定的
其余决策属性在上下文无关语言中是不可判定的。
确定性属性: 上下文无关语言可以是:
- DCFL-确定性(可由确定性下推自动机识别)上下文无关语言
- 非确定性(不能被 DPDA 识别，但 NPDA)上下文无关语言。
版权属于：月萌API www.moonapi.com，转载请注明出处
