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 |

Re: Kleene's Theorem November 07, 2007 10:28PM |
Registered: 13 years ago Posts: 98 Rating: 0 |

Re: Kleene's Theorem November 07, 2007 10:48PM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

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

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 |

Re: Kleene's Theorem November 08, 2007 08:13AM |
Registered: 13 years ago Posts: 98 Rating: 0 |

Re: Kleene's Theorem November 08, 2007 09:04AM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

Re: Kleene's Theorem November 08, 2007 08:02PM |
Registered: 11 years ago Posts: 3 Rating: 0 |

Re: Kleene's Theorem November 08, 2007 10:19PM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

Re: Kleene's Theorem November 09, 2007 08:31AM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

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

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 |

Re: Kleene's Theorem November 10, 2007 08:16PM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

Anonymous User
Re: Kleene's Theorem November 10, 2007 11:29PM |
Rating: 0 |

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

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 |

Re: Kleene's Theorem November 11, 2007 12:19PM |
Registered: 13 years ago Posts: 98 Rating: 0 |

Sorry, only registered users may post in this forum.