偶数个 a 和偶数个 b 构成的 a、b 串的集合 L 一、正则表达式： (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)* 二、右线性表达： 设(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*的右线性表达式为 S0 其中(aa|bb)*的右线性表达式为 S1； ((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*的右线性表达式为 S2； (ab|ba)的右线性部分表达式为 S3 1、对(aa|bb)*部分 S1： 设 aa 部分为 S4，bb 部分为 S5，则 ①、对 S4： S4->aA A->a ②、对 S5： S5->bA A->b ③、对 S1： S1->S4S1|S5S1|ε 2、对(ab|ba)部分 S3： 设 ab 部分为 S6，ba 部分为 S7，则 ①、对 S6： S6->aA A->b ②、对 S7： S7->bA A->a 

③、对 S3： S3->S6|S7 3、设(ab|ba)(aa|bb)*(ab|ba)(aa|bb)*部分为 S8 对 S8： S8->S3S9 S9->S1S10 S10->S3S11 S11->S1 4、对((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*部分 S2： 则 S2->S8S2|ε 5、对(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*部分 S0： S0->S1S12 S12->S2 三、DFA 形式： A：偶数个 a，偶数个 b 的 a、b 串 B：奇数个 a，偶数个 b 的 a、b 串 C：偶数个 a，奇数个 b 的 a、b 串 D：奇数个 a，奇数个 b 的 a、b 串