Welcome! Log In Create A New Profile

# Kleene's Theorem

Posted by Tracey
Announcements Last Post
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Kleene's Theorem November 07, 2007 07:57PM Registered: 13 years ago Posts: 3,249 Rating: 0
I'm trying to understand Kleene's Theorem - where you convert regular expressions into FA's - proof of Rule 2, page 109.

Does anybody have any helpful tips on how to make this easier to understand?
 Re: Kleene's Theorem November 07, 2007 10:28PM Registered: 13 years ago Posts: 98 Rating: 0
Afraid I can't think of another way to explain it better than Cohen does. Maybe if you have specific questions I can help.

Creating an FA3 from FA1+FA2 is actually not as bad as FA1FA2 or FA*..things get pretty hairy with the latter 2.
 Re: Kleene's Theorem November 07, 2007 10:48PM Registered: 13 years ago Posts: 3,249 Rating: 0
I was going through the first example where th input is run concurrently on both FA's and it was just getting too difficult to follow. Do you just alternate a's and b's on each state?
 Re: Kleene's Theorem November 07, 2007 11:32PM Registered: 13 years ago Posts: 98 Rating: 0
Each new state in FA3 is a combination of states from FA1 and FA2 in the following form eg.
z1 = x1 or y1 where x1 and y1 are start states for FA1 and FA2 respectively.

then you have to trace an a from x1 to xsomething and then trace an a from y1 to ysomething. You will now have a state called xsomething or ysomething. If this state is not the same as z1 (ie x1 or y1) then it becomes a new state called z2 so
z2 = xsomething or ysomething

You can now say in your transition table that an a takes you from z1 to z2. You do exactly the same for input leter b.

you have to trace a b from x1 to xsomething and then trace a b from y1 to ysomething. You will now have a state called xsomething or ysomething. If this state is not the same as z1 (ie x1 or y1) or z2 then it becomes a new state called z3 so
z3 = xsomething or ysomething.

You can now say in your transition table that a b takes you from z1 to z3.

This whole process is then repeated for the next state ie. z2, you trace a and b through the xsomething and ysomething of z2 to either create a new state or check that the state doesn't already exist. Eg an a through state z2 might take you back to z2 in which case a new state is not created.

And so on and so on for each zsomething.

Hope this helps

CLive
 Re: Kleene's Theorem November 08, 2007 08:07AM Registered: 13 years ago Posts: 3,249 Rating: 0
Yes, I think it does, thanks!
So you just alternate a's and b's?
 Re: Kleene's Theorem November 08, 2007 08:13AM Registered: 13 years ago Posts: 98 Rating: 0
Yep.. pretty much!
 Re: Kleene's Theorem November 08, 2007 09:04AM Registered: 13 years ago Posts: 3,249 Rating: 0
okay, I'll have another look tonight and hopefully I'll "get" it.
 Re: Kleene's Theorem November 08, 2007 08:02PM Registered: 11 years ago Posts: 3 Rating: 0
The key really is the transition tables - just ignore every thing else until you have made the new states from the combinations and don't panic!!! It comes quite easily after a while for all of them.

Stuart
 Re: Kleene's Theorem November 08, 2007 10:19PM Registered: 13 years ago Posts: 3,249 Rating: 0
Its starting to make some sense now
 Re: Kleene's Theorem November 09, 2007 08:31AM Registered: 13 years ago Posts: 3,249 Rating: 0
I've gone through two examples in the textbook - one of where the input runs on both FA's simultaneously and the other where it starts on FA1 then either goes across to FA2 or stays on FA1.
Thnis might be a stupid question but how do we know which one they're asking for?
 Re: Kleene's Theorem November 09, 2007 08:47AM Registered: 13 years ago Posts: 98 Rating: 0
For the input running simultaneously on FA1 and FA2 the question could be

Find FA3 where FA3 = FA1+FA2 or find an FA which equals to the sum of FA1 and FA2.

For the input first running on FA1 and then on FA2 (or on both), it is the product of FA1 and FA2.

or find FA3 where FA3 = FA1FA2 or find the product (or concatenation) of FA1 and FA2.

or we may also be asked to a convert some regular expression such as a*(a+b)* into an FA, in which case you have to use a combination of all the rules ie r1+r2, r1r2 and r*.
 Re: Kleene's Theorem November 09, 2007 09:00AM Registered: 13 years ago Posts: 3,249 Rating: 0
okay, thanks.
 Re: Kleene's Theorem November 10, 2007 08:16PM Registered: 13 years ago Posts: 3,249 Rating: 0
I'm stuck on the algorithm to chnage the FA from one for R to one for R*. I understand the example but the algorithm is confusing me. On page 129 of the textbook, step 1, what do they mean by 'create a state for every subset of x's' - what is a subset?
 Anonymous User Re: Kleene's Theorem November 10, 2007 11:29PM Rating: 0
subset - A set whose members are members of another set; a set contained within another set

I have a memory resident program on my pc called wordweb. It's extremely helpful for an instant word definition. All I do is ctrl + right click over the word and I have it.
 Re: Kleene's Theorem November 11, 2007 10:32AM Registered: 13 years ago Posts: 98 Rating: 0
I reckon if you can understand how to find FA* for FA and your answers are correct then ignore the algorithm.

but if you really want to know here goes.

eg there are three states x1 and x2 and x3
a state for every subset of x's would be
x1 = Z1
x1 or x2 = Z2
x1 or x3 = Z3
x2 = Z4
x2 or x1 = Z5
x2 or x3 = Z6
x3 = Z7
x3 or x1 = Z8
x3 or x2 = Z9

now some of these states are not needed so they are cancelled. ie cancel any subset (xsomething or ysomething) that contains a final x state, but does not contain the start state.

what you do when working through the example is only find the needed states whereas the algorithm route finds all possible subset states then eliminates the unneeded ones.

Hope this helps
 Re: Kleene's Theorem November 11, 2007 12:11PM Registered: 13 years ago Posts: 3,249 Rating: 0
That definitely helps me understand, thanks so much.
 Re: Kleene's Theorem November 11, 2007 12:19PM Registered: 13 years ago Posts: 98 Rating: 0
Any time...glad it helps
Sorry, only registered users may post in this forum.

Click here to login