regex - 如何使用 Arden 定理获得此 DFA 的 RE?无法获得所需的正则表达式
问题描述
所需的 RE:0*10*1(1+00*1)*
与我得到的 RE0*1(0 + 11* 0)*11*
q0 = q0 0 + ε equ (1)
q1 = q0 1 + q1 0 + q2 0 equ (2)
q2 = q1 1 + q2 1 equ (3)
q0 = ε + q0 0 R=Q+RP
q0 = ε 0* R=QP*
q0 = 0* εR*=R*
q2 = q1 1 + q2 1
q2 = q1 11* equ (4)
Substitute the value of q2 in equ (2)
q1 = q0 1 + q1 0 + q2 0
q1 = 0*1 + q1 0 + q1 11* 0
q1 = 0*1 + q1 (0 + 11* 0) R=Q+RP
q1 = 0*1((0 + 11* 0)*)* R=QP*
q1 = 0*1(0 + 11* 0)* (R*)*=R*
Substitute the value of q1 in equ (4)
q2 = q1 11*
q2 = 0*1(0 + 11* 0)*11*
我试图解决 DFA 以获得所需的 RE,但无法实现我想要的。
解决方案
您找到的正则表达式是正确的,并且自然地从 DFA 的结构中得出,但要获得您指定的 Desired RE,您需要将 DFA 转换为等效的 DFA:
这个 DFA 相当于你的:我分成q1
了两个状态,q1
并且q1'
,从q1
接收转换q0
和从q1'
接收转换q2
,两者都有相同的转换。(我知道,这不是等价的正式证明,但它是这种证明的基本直觉。)
有了这个 DFA,证明就很简单了:
q0 = q0 0 + ε
= ε0*
= 0*
q1 = q0 1 + q1 0
= 0*1 + q1 0
= 0*10*
q1'= q2 0 + q1' 0
= q2 00*
q2 = q1 1 + q2 1 + q1' 1
= 0*10*1 + q2 1 + q2 00*1
= 0*10*1 + q2 (1 + 00*1)
= 0*10*1 (1 + 00*1)*
推荐阅读
- crashlytics - Crashlytics 控制台显示加载程序、Crashlytics 启用和设置正确但无法获取崩溃报告?
- css - Vuetify:如何在 v-select 中设置所选项目的背景颜色
- javascript - 即使不透明度为 1,元素也会隐藏
- javascript - 添加新目标时如何将Hashtag添加到数据目标的属性中。使用纯JS
- node.js - 节点js从键中获取值
- three.js - 如何使用三个js编辑器通过鼠标对一个对象的平滑轴旋转进行编码
- ruby-on-rails - 我可以重定向失败的 sidekiq 工作人员进行调查吗?
- javascript - 我不能让恐龙跳
- c++ - 常量表达式的计算结果为 -1,不能缩小为类型 'char' [-Wc++11-narrowing] 错误
- jquery - 当克隆元素出现时向下滑动