Solved

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

Posted on 2008-10-21
8
475 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
Independent Software Vendors: 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

Enroll in May's Course of the Month

May’s Course of the Month is now available! Experts Exchange’s Premium Members and Team Accounts have access to a complimentary course each month as part of their membership—an extra way to increase training and boost professional development.

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 …
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computers…
Explain concepts important to validation of email addresses with regular expressions. Applies to most languages/tools that uses regular expressions. Consider email address RFCs: Look at HTML5 form input element (with type=email) regex pattern: T…
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…

752 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