Announcements Last Post
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Kleene's Theorem
November 07, 2007 07:57PM
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
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
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
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
Yes, I think it does, thanks!
So you just alternate a's and b's?
Re: Kleene's Theorem
November 08, 2007 08:13AM
Yep.. pretty much!
Re: Kleene's Theorem
November 08, 2007 09:04AM
okay, I'll have another look tonight and hopefully I'll "get" it.
Re: Kleene's Theorem
November 08, 2007 08:02PM
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
thumbs upIts starting to make some sense now
Re: Kleene's Theorem
November 09, 2007 08:31AM
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
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
okay, thanks.
Re: Kleene's Theorem
November 10, 2007 08:16PM
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
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
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
That definitely helps me understand, thanks so much.
Re: Kleene's Theorem
November 11, 2007 12:19PM
Any time...glad it helps
Sorry, only registered users may post in this forum.

Click here to login