正则语言

正则语言所属现代词，指的是形式语言理论中最简单的语言类，是上下文无关语言类的一个真子类，在乔姆斯基语言分层中处于最低层。词语简介形式语言理论中最简单的语言类，是上下文无关语言类的一个真子类，在乔姆斯基语言分层中处于最低层。又称 3型语言。正则语言有两种描述方法:①文法描述;②正则表达式与接受器。正则语言已应用于计算机程序语言编译的词法分析、开关电路设计等方面。描述方法文法描述:正则语言由正则文法(或称右线性文法，见形式语言理论)所生成。当限制产生式形式为A→Bt或A→t时,文法为左线性文法(其中A,B是非终结符,t是终结符)。每一右线性文法必有与之等价的左线性文法存在，即是说，这两种文法生成相同的语言。正则表达式与接受器:正则语言是正则集，可以用称为正则表达式的简单式子来表示。对任意一个给定的正则表达式可以构造出不确定有限自动机来接收它，反过来，从任意有限自动机可以找出它所接受的正则表达式。正则表达式 正则表达式描述的语言是正则集。令∑是一个有限集，递归地定义如下:①φ、ε、ɑ(凬ɑ∈∑)是∑上的正则表达式,它们所表示的字集分别为空集，{ε}、{ɑ}