ایجاد: 1398/11/27 18:20 - ویرایش: 1399/4/3 19:37
A
A
ساده سازی عبارات منظم در نظریه محاسبات
رشته خالی: λ
قوانین
همانی
λa = aλ = a
a+a = a
a+λ != a
جا به جایی پذیری
a+b = b+a
ab != ba
شرکت پذیری
a+(b+c) = (a+b)+c = a+b+c
a(bc) = (ab)c = abc
a+(bc) != (a+b)c
توزیع پذیری
a(b+c) = ab+ac
(a+b)(a+b) = aa+ab+ba+bb
a+(bc) != (a+b)(a+c)
در جمله A+B، اگر A زیر مجموعه ای از B باشد حذف می شود.
a+(b+a) = b+a
λ+a* = a*
λ+(λ+a+aa+...) = λ+a+aa+...
(a+λ)* = (a)* = a*
(ab+λ+aab)*
(ab+aab)*
a+aa* = aa*
a+(a+aa+...) = a+aa+...
a*a*a* = a*a* = a*
(λ+a+aa+...)(λ+a+aa+...)(λ+a+aa+...)
a*+aa*+aaa*+... = a*
پرانتز قرینه
a(ba)* = (ab)*a
a*(ba*)* = (a*b)*a*
b*a(bb*a)* = b*(abb*)*a = (b*ab)*b*a
موارد دیگر
λ+aa* = a*
λ+(a+aa+...) = λ+a+aa+...
b+aa*b => (λ+aa*)b => a*b
b*+b*aa* => b*(λ+aa*) => b*a*
a*aa* = a*a = aa*
(a+b)* = a*(ba*)* = (a*b)*a*
a*ba*(ba*ba*)*
a*b(a+ba*b)*
(a+b)* = (a+b*)* = (a*+b)* = (a*+b*)*
(a+b)* = (a*b*)* = (b*a*)*
(a+b)* = (a*b)* + (b*a)*
(a+b)* = a*b*(a+b)*b*a*
(a+b)* = (a*b)*a*(ba*)* = (b*a)*b*(ab*)*
(a+b)* = (a*b)*(a*b)*a* = (b*a)*(b*a)*b*
(a+b)* = (a+b)*(ba*)*
(a+b)* = (ab+b)*(a+b)*
نکته
a* => λ+a+aa+...
aa* => a+aa+aaa+...
aaa* => aa+aaa+...