Kleene's Theorem

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?

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.

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?

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

Yes, I think it does, thanks!
So you just alternate a's and b's?

Yep.. pretty much!

okay, I'll have another look tonight and hopefully I'll "get" it.

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

Its starting to make some sense now

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?

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*.

okay, thanks.

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?

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.

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

That definitely helps me understand, thanks so much.

Any time...glad it helps