Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

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

Posted on 2008-10-21
8
Medium Priority
?
512 Views
Last Modified: 2011-10-19
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
Comment
Question by:corthezz
  • 5
  • 2
8 Comments
 
LVL 22

Expert Comment

by:Brian Utterback
ID: 22775577
I don't see an attached PDF file.
0
 

Author Comment

by:corthezz
ID: 22775624
The solution is somewhere in the PDF
oporaTCS.pdf
0
 
LVL 22

Expert Comment

by:Brian Utterback
ID: 22776087
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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 

Author Comment

by:corthezz
ID: 22776257
union

take a look at pages 10, 11, 14, 38, 39,40... near these pages are the answers in attached PDF
0
 

Author Comment

by:corthezz
ID: 22776270
a* = U A^n, where n >= 0
0
 

Author Comment

by:corthezz
ID: 22776296
i must get the prove in Kleene algebra or in regular expressions
0
 
LVL 22

Accepted Solution

by:
NovaDenizen earned 2000 total points
ID: 22815920
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
 

Author Comment

by:corthezz
ID: 22815960
Thank you! This is what i looked for....... btw i must completed it until today 18:00 ;)
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Dependencies in Software Design In software development, the idea of dependencies (http://en.wikipedia.org/wiki/Coupling_%28computer_programming%29) is an issue of some importance. This article seeks to explain what dependencies are and where they …
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

972 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question