• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 520
  • Last Modified:

Proove in Kleene algebra the term a*=(aa)*+a(aa)*

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
0
corthezz
Asked:
corthezz
  • 5
  • 2
1 Solution
 
Brian UtterbackPrinciple Software EngineerCommented:
I don't see an attached PDF file.
0
 
corthezzAuthor Commented:
The solution is somewhere in the PDF
oporaTCS.pdf
0
 
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
The new generation of project management tools

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.

 
corthezzAuthor Commented:
union

take a look at pages 10, 11, 14, 38, 39,40... near these pages are the answers in attached PDF
0
 
corthezzAuthor Commented:
a* = U A^n, where n >= 0
0
 
corthezzAuthor Commented:
i must get the prove in Kleene algebra or in regular expressions
0
 
NovaDenizenCommented:
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

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

  • 5
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now