正则文法:又称为
3型文法。这种
文法分为两种类型:第一类要求生成式的形式必须是A→ωB或A→ω,其中A,B都是变元,ω是
终结符串,这种特殊的正则文法称为右线性文法。第二类正则文法称为
左线性文法,它要求生成式必须是A→Bω,或A→ω的形式。由正则文法生成的语言称为
正则语言,它恰是
有穷自动机所识别的语言类。
正则文法:又称为
3型文法。这种
文法分为两种类型:第一类要求生成式的形式必须是A→ωB或A→ω,其中A,B都是变元,ω是
终结符串(可以是空串),这种特殊的正则文法称为右线性文法。第二类正则文法称为
左线性文法,它要求生成式必须是A→Bω,或A→ω的形式。由正则文法生成的语言称为
正则语言,它恰是
有穷自动机所识别的语言类。
在计算机科学中,正则文法是产生式规则取下述形式的一种
形式文法(N, Σ,P,S):
正则文法描述的语言构成了正则语言类,正则语言类中的语言也可以由
有限状态自动机或
正则表达式来表达。
正则语言又称正规语言是满足下述相互等价的一组条件的一类
形式语言: