ساده سازی عبارات منظم در نظریه محاسبات

رشته خالی: λ

تولید تصادفی ورودی ساده سازی گام به گام

قوانین

همانی

λa = aλ = a a+a = a a+λ != a

جا به جایی پذیری

a+b = b+aab != ba

شرکت پذیری

a+(b+c) = (a+b)+c = a+b+ca(bc) = (ab)c = abca+(bc) != (a+b)c

توزیع پذیری

a(b+c) = ab+ac (a+b)(a+b) = aa+ab+ba+bba+(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)*aa*(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*bb*+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+...