Solved

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

Posted on 2008-10-21
468 Views
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
Question by:corthezz
• 5
• 2

LVL 22

Expert Comment

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

Author Comment

ID: 22775624
The solution is somewhere in the PDF
oporaTCS.pdf
0

LVL 22

Expert Comment

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

Author Comment

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

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

Author Comment

ID: 22776296
i must get the prove in Kleene algebra or in regular expressions
0

LVL 22

Accepted Solution

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

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

## Featured Post

Question has a verified solution.

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

Before You Read The Article Please make sure you understand these two concepts: Variable Scope (http://www.php.net/manual/en/language.variables.scope.php) and Property Visibility (http://www.php.net/manual/en/language.oop5.visibility.php).  And to …
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
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…