偶数个a和b的正则表达式、右线性表达、及DFA
需积分: 43 35 浏览量
2018-01-16
23:17:03
上传
评论 1
收藏 62KB DOCX 举报
偶数个 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)* 部分为 S 8
资源评论
