上下文无关语言的可重复序列及其性质  

Properties of Repetitive Sequences for Context-free Language

作　　者：张继军[1] 范昊[1] 

机构地区：[1]山东农业大学信息科学与工程学院,山东泰安271018

出　　处：《小型微型计算机系统》2010年第6期1226-1230,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60673053)资助;国家自然科学基金委员会重大研究计划项目(90718011)资助

摘　　要：通过分析下推自动机的运行规律和特点,提出上下文无关语言的可重复序列的概念,将其划分为平衡重复序列、增重复序列、减重复序列三类;研究了这三类可重复序列在下推自动机的状态转换图中的结构表现和性质,通过分析下推自动机状态转换图中标注回路与可重复序列之间的关系,给出求解可重复序列的计算方法;证明了不同类型的可重复序列对上下文无关语言性质的影响,利用可重复序列揭示了上下文无关语言的Pumping引理的本质特征,并给出正规语言判定的一个充分必要条件.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 kinds of repetitive sequence to context-free language,reveals the original feature of Pumping lemma for context-free languages by the properties of repetitive sequence.Finally,it gives the sufficient and necessary conditions of determining regular language.

关 键 词：可重复序列 Pumping引理 状态转换图 上下文无关语言 

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