Assignment 1 Question 8

Hey been doing assignment 1 and needed to ask your opinion on Q8.
they say that S* is defined by (bb)*(abba* +aba)*
then ask, wish of the following words are in the language?
I cant seem to fit any of the options given..

Am I incorrect or is there something wrong with the question.

Many thanks

Danie van Eeden
------------------------

I could be wrong, but this is one for which I do have an answer. (Don't think I could go much further than that without raising plagiarism issues etc).

umm OK, parsing it, it can have as many double bb's as you like or none. Then for the purposes of this question, it could have some or none of the next set of options boils down to "some".

Each time you've gotten to the end of making a substring of the second part, you chose again: The one on the left? The one on the right.

So what's on the left? You must have abb if you pick this left side one. You can also optionally add
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa to your heart's content. However, if you pick the right side of + you may only use an aba.

Of course you could then use the * and produce abaabaabaabaabaabaabaaba .....

I'm pretty sure now that it does have an answer. Just look carefully at what substrings are available at each iteration, and you'll find a match.

Now from my part, the reason I haven't sent off my answers yet is that I remain stuck on questions 5 and 9.

OK so we can have as many generators as we like, so as long as one of the ones one COULD use are on the list I suppose the answer's OK. And it does look like you HAVE an answer to Q5, if you're already at Q8?

Im an idiot! thank you again..

(bb)*(abba* +aba)* was given
and I read (ever so enthusiatically) (bb)*((abba)* +aba)*

Ok - regarding 5 & 9. sometimes I just skip ahead en then go back - but yes I figure Ive got 5 & 9...
my theories to follow: without giving away the answer (cause Im afraid some of the moderators on the forum might not like it)
PM me an I'll try explaining better

Q5: the language is EVEN without containing BAB. I keep in mind that AB, BA, AA, BB is also even, and does not contain the substring BAB. Hence it must be a generator (even though not listed). The language must list all EVEN without BAB.

Q9: I follow the same theory here. I keep in mind that there are shorter generators than aba, baa, aaa that are odd and do not contain BAB. I also keep in mind the option that was available in Q5. Empty set must either be even or odd. Our book states that its EVEN, hence it cant be ODD / optional here.

hope this helps.

Danie van Eeden
------------------------

Thanks Danie.
I actually hate getting just-the-answer, so your way of putting it suits me down to the ground. At very least I'll have done some Thinking, once I've tried to work it through. I think that's the whole point. The course is meant to give us things to think about, and as long as that's what we're doing (as opposed to memorising set answers to exam questions etc), I can't see how there can be real problems with discussing the assignments.

It would be nice to be discussing stuff more general than this, but hey, the first order of business is to survive. In a sense this yearmark idea has ruined the intellectual aspect of assignment submission (because surviving and thinking can be at odds in quite a big way, often).

Patience, patience. Probably my problem with Q5 etc is also just a patience problem.

because surviving and thinking can be at odds in quite a big way, often

yup I agree.
chat again soon.

Danie van Eeden
------------------------

Thanks. Have submitted my best possible answers. Hopefully the machine that marks them will not be too contemptuous of them.