Assignment4 q3

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???

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)'

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)' ??

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.

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.

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?

OHHH!!! just got now, Please check the end of question 5, it states "Why is this problem wrong? How can it be fixed?"

I didn't answer the last part of the question, wanted to but forgot about it.

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.

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.

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

I'm repeating this subject, so I have last year's tut's as examples. Not all my thinking.

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.