上下文无关语言的同步运算及其性质  

作　　者：冯靓静 

机构地区：[1]山东大学计算机学院,济南250101

出　　处：《电脑编程技巧与维护》2017年第9期5-8,11,共5页Computer Programming Skills & Maintenance

摘　　要：针对上下文无关语言,引入了语言的可重复序列的依赖运算和同步运算,分析了两种运算的性质、特点,给出了可重复序列的依赖表达式、同步串约束表达式;提出了同步串约束上下文无关语言,给出了该类语言的构造规则:对于字母表上的同步串约束上下文无关语言L,都是由该字母表上的一个正规语言R与该正规语言R中某些可重复序列之间的依赖约束所形成的;证明了同步串约束上下文无关语言与同步串约束表达式所描述的语言等价,且该类语言是上下文无关语言的真子集。

关 键 词：同步运算 依赖运算 依赖表达式 同步串约束表达式 同步串约束上下文无关语言 

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构]