# Assignment4 q3

Posted by giggs
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
 Assignment4 q3 July 19, 2007 01:18PM Registered: 13 years ago Posts: 88 Rating: 0
Did anyone manage to prove the equivalent? coz i got two FA's that do not accept anything and the other one accept null... i'm a lost???
 Anonymous User Re: Assignment4 q3 July 19, 2007 01:29PM Rating: 0
To test for equivalence between the two FA's, set them out in the formula below and evaluate them in a boolean fashion:
(FA1' + FA2)' + (FA2' + FA1)'
 Re: Assignment4 q3 July 19, 2007 01:44PM Registered: 13 years ago Posts: 88 Rating: 0
I used the same formula, and (FA1'+FA2)' gives NULL
and (FA1' + FA2)' gives nothing

but in this case if one accept NULL and the other except empty string, the two are not equivalent.
Did u get an empty string in both (FA1'+FA2)' and (FA1' + FA2)' ??
 Anonymous User Re: Assignment4 q3 July 19, 2007 02:11PM Rating: 0
I worked out each FA and it's complement (drew 4 FA's). Then I drew each bracketed expression and it's complement (another 4 FA's). I was then in a position to evaluate my expression. It evaluated to TRUE and so I said my FA's were equivalent.
 Re: Assignment4 q3 July 19, 2007 02:15PM Registered: 13 years ago Posts: 3,015 Rating: 5
If the language (L1Ã¢â‚¬â„¢ + L2)Ã¢â‚¬â„¢ + (L2Ã¢â‚¬â„¢ + L1)Ã¢â‚¬â„¢ is empty, then the two FAs is equivalent. If the language is not emptly, then the two FAs is not equivalent.
For (FA1Ã¢â‚¬â„¢ + FA2) there are three final stages and for (FA1Ã¢â‚¬â„¢ + FA2)Ã¢â‚¬Ëœ there is a final state. When combined with (FA2Ã¢â‚¬â„¢ + FA1)Ã¢â‚¬â„¢, the new combined FA would also have a finale state. So, there will be words that could be accepted by the machine and thus the language is not empty.
Therefore, the given FA1 and FA2, are not equivalent.
 Anonymous User Re: Assignment4 q3 July 19, 2007 02:24PM Rating: 0
Reanie Wrote:
-------------------------------------------------------
> If the language (L1Ã¢â‚¬â„¢ + L2)Ã¢â‚¬â„¢ + (L2Ã¢â‚¬â„¢ + L1)Ã¢â‚¬â„¢
> is empty, then the two FAs is equivalent.

I think I missed that part in the book? That doesn't make sense to me. Is there some proof of this?
 Re: Assignment4 q3 July 19, 2007 02:25PM Registered: 13 years ago Posts: 88 Rating: 0
OHHH!!! just got now, Please check the end of question 5, it states "Why is this problem wrong? How can it be fixed?"
 Re: Assignment4 q3 July 19, 2007 02:29PM Registered: 13 years ago Posts: 3,015 Rating: 5
I didn't answer the last part of the question, wanted to but forgot about it.
 Anonymous User Re: Assignment4 q3 July 19, 2007 02:30PM Rating: 0
Ja, I said that there is an unnecessary circuit formed in FA1. The b edge returning to the start state should be looped onto the state from where it originates.
 Re: Assignment4 q3 July 19, 2007 02:33PM Registered: 13 years ago Posts: 3,015 Rating: 5
Rick Wrote:
-------------------------------------------------------
> Reanie Wrote:
> --------------------------------------------------
> I think I missed that part in the book? That
> doesn't make sense to me. Is there some proof of
> this?

Rick, I've sent you an email. I'll check the correct proof tonight and post it here.
 Re: Assignment4 q3 July 19, 2007 02:41PM Registered: 13 years ago Posts: 88 Rating: 0
Reanie Wrote:
-------------------------------------------------------
> If the language (L1Ã¢â‚¬â„¢ + L2)Ã¢â‚¬â„¢ + (L2Ã¢â‚¬â„¢ + L1)Ã¢â‚¬â„¢
> is empty, then the two FAs is equivalent. If the
> language is not emptly, then the two FAs is not
> equivalent.
> For (FA1Ã¢â‚¬â„¢ + FA2) there are three final stages
> and for (FA1Ã¢â‚¬â„¢ + FA2)Ã¢â‚¬Ëœ there is a final state.
> When combined with (FA2Ã¢â‚¬â„¢ + FA1)Ã¢â‚¬â„¢, the new
> combined FA would also have a finale state. So,
> there will be words that could be accepted by the
> machine and thus the language is not empty.
> Therefore, the given FA1 and FA2, are not
> equivalent.

Thanks Reanie... and u guys 4 the feed back. Rick, i hope u also got something...
 Re: Assignment4 q3 July 19, 2007 02:47PM Registered: 13 years ago Posts: 3,015 Rating: 5
I'm repeating this subject, so I have last year's tut's as examples. Not all my thinking.
 Re: Assignment4 q3 July 19, 2007 03:21PM Registered: 13 years ago Posts: 3,015 Rating: 5
I've downloaded the study guide from MyUnisa - the Afr version, but the pages should be more-or-less the same.
On p71-72 Chp 11 are being described and how to do the sums.
On p133-141 examps have been worked out. Especially ex 6 is the same scenario as (I think) we had.
Sorry, only registered users may post in this forum.