Solved

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

Posted on 2008-10-21
8
483 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 2
8 Comments
 
LVL 22

Expert Comment

by:blu
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:blu
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

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 500 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

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
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…
Suggested Courses
Course of the Month10 days, 17 hours left to enroll

631 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