Please someone, who knows the Kleene algebra. I must prove that the term (aa)*+a(aa)* equals a*. Can anybody help me? There are some theorems, what you must use. In that attached PDF are the theorems
Brian UtterbackPrinciple Software EngineerCommented:
I need a little clarification on the use of the "+" here. In regular expressions, the "+" operator is used to designate "one or more",
which is to say formally:
a+ <=> aa*
It can also be used to designate concatenation, that is
a+b <=> ab
And it can also be used to designate the union of two sets:
A + B <=> A union B
Can you say which usage is meant here?
0
With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.
let X = (aa)* + a(aa)*
To prove equivalence with a*, you need to show X <= a* and a* <= X.
I suspect this might be schoolwork, so I'll only do the first half. :)
a* = a*
a* = a* + a*
by definition of <=
a* <= a*
note that for any X, X <= X.
apply A.10 twice
1 + aa* <= a*
1 + a + aaa* <= a*
(1 + a) + (aa)a* <= a*
by A.12
(aa)*(1+a) <= a*
(aa)* + (aa)*a <= a*
by R.17
(aa)* + a(aa)* <= a*
X <= a*
Now just prove a* <= X similarly. Start with X <= X, then get to an application of A.12 that results in a*1 <= X. Once that's done, you can conclude that a* = X.
0
corthezzAuthor Commented:
Thank you! This is what i looked for....... btw i must completed it until today 18:00 ;)
0
Featured Post
Be seen. Boost your question’s priority for more expert views and faster solutions