Assignment 4, Question 1

I am a bit stuck on this question. I have worked out L₁' as well as L₂' and the FA for each of these.
I have also worked out (what I think to be correct), the FA for L₁'+ L₂'. 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?)

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

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?

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.

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

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.

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.

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

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.

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

Reanie

The subject news for COS201 you are reffering to actually says "Question 4 Assignment 1" and not Question 1 Assignment 4.

Ms Liang has corrected the subject news after my post.