# Assignment 4, Question 1

Posted by InSaNiE
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
 Assignment 4, Question 1 June 27, 2007 10:27PM Registered: 13 years ago Posts: 81 Rating: 0
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?

(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 Registered: 12 years ago Posts: 191 Rating: 0
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 Registered: 13 years ago Posts: 81 Rating: 0

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?
 Re: Assignment 4, Question 1 June 28, 2007 03:22PM Registered: 13 years ago Posts: 3,015 Rating: 5
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 Registered: 12 years ago Posts: 191 Rating: 0
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 Registered: 13 years ago Posts: 81 Rating: 0
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 Registered: 13 years ago Posts: 119 Rating: 0
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 Registered: 12 years ago Posts: 191 Rating: 0
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 Registered: 13 years ago Posts: 81 Rating: 0
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.
 Re: Assignment 4, Question 1 June 29, 2007 01:13PM Registered: 13 years ago Posts: 3,015 Rating: 5