22-正规文法与正规语言

形式语言与自动机理论2010-2011第2章正规文法与有限自动机正规语言是Chomsky文法体系中最简单的一类语言。产生这种语言的文法是正规文法，识别这类语言的是有限自动机。此外，这类语言也可以用正规表达式表示。2.1正规文法和正规语言正规文法是Chomsky文法体系中最简单的一种文法。说它简单，是指它的产生式的形式简单，因为产生式集是一个文法的核心。定义2.3设(,;,)GVTPS为一个文法1）如果G中的每个产生式都有Aw或AwB,,*ABVwT的形式，则称G为一个右线性文法。2）如果G中的每个产生式都有Aw或ABw,,*ABVwT的形式，则称G为一个左线性文法。右线性文法和左线性文法统称正规文法（regulargrammar,RG）。正规文法产生的语言称为正规语言（regularlanguage,RL）。例设({,,},{0,1},,)GSABPS，其中:0|1|10|101|0PSABAABB从各个产生式的具体形式可以看出，G是一个右线性文法，所以是一个正规文法容易证明()(01)*(10)*LG由于这个语言可由一个上下文无关文法产生，所以()LG是一个上下文无关语言。此外，()LG也可以由下面的左线性文法产生：1|0|10|001|1SABAABB正规文法的规范形式定理2.3设G为一个右线性文法，那么存在一个文法'G，使得(')()LGLG而且'G中的产生式都有,,SAaAaB3种形式。其中S是初始符，,AB是变量，a是终极符。推论2.1设G为一个左线性文法，那么存在一个文法'G，使得(')()LGLG而且'G中的产生式都有,,SAaABa3种形式。定理2.3和推论2.1是同一个意思，只不过一个是针对右线性文法，另一个针对左线性文法。它们都指出，左、右线性文法中的产生式右边的串中，不仅变量只能出现一个（最左端，或最右端），而且右边出现的终极符串也可以改为长度最大为1。这个定理和推论的证明思路是很简单的：引入新的变量和新的产生式，把右边长度大于1的产生式分解为终极符串长度等于1的产生式。例如，假若右线性文法中有一个产生式12nAaaaB那么，引入1n个新变量121,,,nEEE，把上面产生式用n个下面的产生式代替111221,,,nnAaEEaEEaB下列各文法生成什么语言？1.S→0SS→02.S→S0S→03.S→SSS→04.S→00SS→ε5.S→00SS→06.S→000SS→ε7.S→0SS→1SS→0S→18.S→0SS→1SS→ε作业试写出下列语言的正规文法:1.以a开头以b结尾的所有a-b串。2.含aaa的所有a-b串。3.{aibjck|i,j,k≥1}