通过应用特性，证明正则表达式的相等性？

题目

证明以下每个正则表达式的相等性。

a. ab*a(a + bb*a)*b = a(b + aa*b)*aa*b。

b. b + ab* + aa*b + aa*ab* = a*(b + ab*).

解法

题目 1

证明 ab*a(a + bb*a)*b = a(b + aa*b)*aa*b。

Let’s take LHS ,
   = ab*a(a + bb*a)*b
Use property of (a+b)* = a*(ba*)*
   = ab*a (a* ((bb*a) a* )* a*b
   = ab* a (a*bb*a)* a*b {Associative property}
   = ab* (a (a*bb*a)*)a*b
   = ab*(aa*bb*)*aa*b
   = a (b*(aa*bb*)*)aa*b
Use property a* (ba*)*= (a+b)*
   = a(b+aa*b)*aa*b
   = RHS
Hence proved

题目 2

证明 b + ab* + aa*b + aa*ab* = a*(b + ab*).

Let’s take LHS,
   = b + ab* + aa*b + aa*ab*
   = (b+aa*b)+(ab*+aa*ab*)
   = (^+aa*)b+(^+aa*)ab* {using distributing property}
   = (a*)b+(a*)ab* from ^+aa*=a*
   = a*b+a*ab*
   = a*(b+ab*) {distributive property}
   = RHS
Hence proved

Bhanu Priya

更新于: 16-6 月-2021

821 次浏览

开启你的 职业生涯

完成课程，获得认证

开始