Welcome! Log In Create A New Profile

Advanced

Assignment 4, Question 1

Posted by InSaNiE 
Announcements Last Post
Announcement myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
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
Assignment 4, Question 1
June 27, 2007 10:27PM
I am a bit stuck on this question. I have worked out L1' as well as L2' and the FA for each of these.
I have also worked out (what I think to be correct), the FA for L1'+ L2'. The problem is each state in this FA is marked as a "final" state, so when trying to find out the complement of this, I have an FA with no "final" state.
Is this wrong - am I missing something?

Thanks in advance.

(for some reason the subscript isn't working correctly - is it just me, or everyone having the problem?)
Re: Assignment 4, Question 1
June 28, 2007 01:22PM
I got the same thing, but I sorta expected it. If you look at r1 and r2, the one is all strings with a double a in it, and the other is all strings without a double a in it.

Also, FA1 looks like FA2'.

So, it sorta makes sense to me that the language will be empty.
I think I saw that they won't mark this question, though.

Regards,
JB
Re: Assignment 4, Question 1
June 28, 2007 02:53PM
Thanks for replying JB

Yeah, I been thinking about the question, and it does make sense that the language is empty, because the r1 and r2 (and the FA's) are "opposite" to one another.

But I guess what I'm getting at is: once I get to the point where I have the FA for L1' + L2' ..whats the next step? The FA for (L1' + L2')' has no "final" state, so I'm not sure how to get a regular expression from this?

Any confirmation that the question wont be marked?
avatar Re: Assignment 4, Question 1
June 28, 2007 03:22PM
I think this one is not going to marked. On the "registered students" page is the following:
COS201-V
31/05/07

Question 1 Assignment 4 - We are aware that there appears to be an error in the question. Full credits will be awarded for this specific question regardless of the answer. Question 5 Assignment 3 - The question should read as follow: "Convert the Mealy machine in problem 6(i) on page 166 of the 1997 edition to a Moore machine." Full credits will be awarded for this question regardless of the answer. Question 4 Assignment 4 - The question should be referring to 13(iii) instead of 10(iii) on page 220 of the prescribed book.
Re: Assignment 4, Question 1
June 28, 2007 03:25PM
InSaNie,

It's been a while since I did the question, but I think I just drew FA1 and FA2. You then go through the steps as though you are making a machine that is the union of FA1 and FA2, but with a few exceptions. Cohen describes this way after he finishes the way (I think) you are using.
From what I understand, you are going the (L1' + L2')' route? Right?
I don't have the book with me, so unfortunately I can't give you page numbers...

JB
Re: Assignment 4, Question 1
June 28, 2007 06:55PM
Thanks Reanie - wont stress too much about it now.

JB - yeah, Ive gone the (L1' + L2')' route. I've drawn up the FA for L1' + L2', but then to get to (L1' + L2')' you switch all non-final state to final, and all final to non-final. The problem is my FA for L1' + L2' has all final state, so switching them, I got a FA with all non-final states..was a bit stuck then, as to how to get a regular expression from that. But if there is an error in the question - no worries. But thanks very much for the input.
Re: Assignment 4, Question 1
June 29, 2007 11:50AM
The following posting on the module news was incorrect:
"Question 1 Assignment 4 - We are aware that there appears to be an error in the question. Full credits will be awarded for this specific question regardless of the answer."

It was meant for Question 4, Assignment 1. We apologise for the error.
Re: Assignment 4, Question 1
June 29, 2007 12:07PM
InSaNie,
You can now continue to stress. 8^>

If you consider a Venn diagram, with L1 being everything in a circle, then L2 ( == L1') will be everything outside the circle. There aren't two circles, only one circle. So, the intersection between L1 and L2 must be empty. (There are no strings in L1 that are also in L2.)

The regular exp. I used was r3 = (phi) (the o with a dash through it.) Referrring to earlier in the book, this is an empty language, if I am not very much mistaken. A FA without final states cannot accept any strings, so the language must be empty.

Again, when you internalise the fact that L1 == L2', it becomes clear.
Let me know if you still have problems.

JB
Re: Assignment 4, Question 1
June 29, 2007 12:56PM
Liang - thanks for the update. Btw, where is this "module news" page, I can't seem to find it anywhere. I must be blind.

JB, thanks for the input. It all makes complete sense to me, as to why there is no final state (because, as you said L1 == L2' , so effectively we have (L1 OR L1') which is all string. If we "NOT" that we get a language with no string). All makes sense, what wasn't making sense was how to put that into a regular expression (and I knew there had to be a regular expression, as (L1' + L2')' is regular)
But I'll go with your advice as to what r3 comes out as - so thanks again.
avatar Re: Assignment 4, Question 1
June 29, 2007 01:13PM
General news on this page:
http://osprey.unisa.ac.za/reg.htm
You can select your subjects on the right and then you get the relevant subject's news in the middle and phorum and download on the left.
And the specific subject page:
http://osprey.unisa.ac.za/mod.htm?qcode=COS201-V
Re: Assignment 4, Question 1
July 09, 2007 06:45PM
Reanie

The subject news for COS201 you are reffering to actually says "Question 4 Assignment 1" and not Question 1 Assignment 4.
avatar Re: Assignment 4, Question 1
July 09, 2007 10:45PM
Ms Liang has corrected the subject news after my post.
Sorry, only registered users may post in this forum.

Click here to login