| 上下文无关语言的可重复序列及其性质 |
| |
| 引用本文： | 张继军,范昊.上下文无关语言的可重复序列及其性质[J].小型微型计算机系统,2010,31(6). |
| |
| 作者姓名： | 张继军 范昊 |
| |
| 作者单位： | 山东农业大学,信息科学与工程学院,山东,泰安,271018 |
| |
| 基金项目： | 国家自然科学基金，国家自然科学基金委员会重大研究计划项目 |
| |
| 摘 要： | 通过分析下推自动机的运行规律和特点,提出上下文无关语言的可重复序列的概念,将其划分为平衡重复序列、增重复序列、减重复序列三类;研究了这三类可重复序列在下推自动机的状态转换图中的结构表现和性质,通过分析下推自动机状态转换图中标注回路与可重复序列之间的关系,给出求解可重复序列的计算方法;证明了不同类型的可重复序列对上下文无关语言性质的影响,利用可重复序列揭示了上下文无关语言的Pumping引理的本质特征,并给出正规语言判定的一个充分必要条件.
|
| 关 键 词： | 可重复序列 Pumping引理 状态转换图 上下文无关语言 |
Properties of Repetitive Sequences for Context-free Language |
| |
| ZHANG Ji-jun,FAN Hao.Properties of Repetitive Sequences for Context-free Language[J].Mini-micro Systems,2010,31(6). |
| |
| Authors: | ZHANG Ji-jun FAN Hao |
| |
| Affiliation: | ZHANG Ji-jun,FAN Hao(College of Information Science , Engineering,Sh,ong Agriculture University,Taian 271018,China) |
| |
| Abstract: | The conception of repetitive sequence of context-free language is introduced,and is divided into equation repetitive sequence,increase repetitive sequence and decrease repetitive sequence.It studies the behavior and properties of these three kinds of repetitive sequence in state transition diagram of pushdown automata,gives the relations between labeled loop in state transition diagram and repetitive sequence and the arithmetic of computing repetitive sequence.It analyses and shows the effects of different ... |
| |
| Keywords: | repetitive sequence pumping lemma state transition diagram context-free language |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
