数据结构
网络技术
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究说明两个正则表达式相等的难题。
问题 1
证明 (1+00*1)+(1+00*1)(0+10*1)*(0+10*)=0*1(0+10*1)*
解答
这里，我们需要证明 LHS=RHS（左端 = 右端）
让我们先求解 LHS
(1+00*1)+(1+00*1)(0+10*1)*(0+10*)
取 (1+00*1) 为公因式
(1+00*1)( ε+(0+10*1)*(0+10*1)
其中：
(0+10*1)*(0+10*1) 的形式为 R*R，其中 R=0+10*1
众所周知，(ε+R*R)=( ε+RR*)=R*
因此，
(1+00*1)((0+10*1)*)
取 1 为公因式
(ε+00*)1(0+10*1)*
应用 ε+00*=0*
0*1(0+10*1)*
=RHS
于是，这两个正则表达式相等。
问题 2
证明 (0*1*)*=(0+1)*
解答
考虑 LHS
(0*1*)*= { ε,0,00,1,11,111,01,10,……}
= {任何 0 的组合，任何 1 的组合，任何 0 和 1 的组合，ε}
类似地
RHS=(0+1)*
= { ε,0,00,1,11,111,01,10,…..}
= { ε，任何 0 的组合，任何 1 的组合，任何 0 和 1 的组合}
因此，证明了
LHS=RHS
更新于：2021-6-12
4K+ 次浏览量
广告