Assignment 1 Question 2

Have I missed something regarding the Kleene closure?

How is it that given a set of letters, it is possible to come up with more occurrences of a word with less “capacity� than another?

I don’t see how one can create such a closure because as I understand it, as the potential capacity of the word increases so do the number of occurrences.

Does anybody know if I am correct in saying that it is impossible to give any examples in response to this question?

I chose my set S = {aba}. That way when you form the closure S*, it can only create words where the length are multiples of 3. So there will be 1 x 3 letter word, 1 x 6 letter word, etc. So there are always 1 six letter word more than, 4 (none), 5 (none), but there will never be more six letter words than 12 letter words.

Does this make sense?

I don't know if this is 100% right.

BTW: Is it just me or do the study guide make chapter 3 more difficult. I don't know if it will help in the later chapters...

That was also my thought until I understood that the set S = {aba} is a set of only a single letter, namely "aba" which would result in a single six letter word (aba six times) as well as a single seven letter one (aba seven times).

If we were to make this set S = {a b a} then we would have a three letter set but forming the closure S* would result in more occurences of seven letter words than six letter ones.

I may however be wrong about seeing the set S = {aba} as one of a single letter.

BTW I haven't had a look at the study guide yet but an expanded explanation and more examples of closures would be nice.

I don't think the set S = {aba} is one single letter.
Can the lecturers please confirm this?
Now you have me confused.

BTW: Are there only 2 students doing COS201 this year?

Hi StevenV and RiaanR

I think some definitions are being confused here. Here's how I see it:

[Sigma] = {set of letters}

S = {set of words}

S* = {set of all concatinated words + empty string}

By analogy, S* would thus be to S as a powerset is to a set.

If my definitions are correct, stevenw, then S = {aba} means you have a dictionary of only one word of length 3 and the word itself being made from a set of only two types of letters.

S* = {^, aba, abaaba, ... } would thus contain concatinated words of length 0, 3, 6, ...

Cheers
Rob

After reading the study guide, I tend to agree with you Rob.

My current understanding is that if you let the set S = {ab, cd, efghi} then you are able to create a closure of 8 possible six letter words (by combining ab and cd in different sequences) and four possible seven letter words (by combining efghi with either ab or cd).

Am I right in this thinking?

I'm not too sure if there other two parts of the question can be answered though: creating a closure with more six letter than eight letter and more six letter than twelve letter words. I'm still working on the problem though ...

Surely for more 6s than 12s you just need to make at least 2 different sets of words with length of 6 because then by combining these two, you get one of 12. Thus you have half as many 12s as 6s.

No, damn, that won't work because "aaaaaabbbbbb" is different from "bbbbbbaaaaaa" so will that be the case with all the 6s? In that case, there will always be equal numbers of 6s and 12s.

I think I've just confused myself

There will always be less or the same amount of 12 letter words than 6 letter words. If your set is multiples of 3.

That's my understanding.

Unless the set of words only have a 12 letter words. then there would be no 6 letter words, and x amount 12 letter words.

Creating a set with multiples of three e.g. S = {3, 6, 9, 12} (those are the lengths, not the words) will result in a closure with more words of length 12 than 6:

length of 6: 33, 6
length of 12: 3333, 66, 39, 93, 12

e.g. S = {abc, defghi, jklmnopqr, stuvwxyztjbi}

The potential closures of specific length are:
S*(6) = {abcabc, defghi}
S*(12) = {abcabcabcabc, defghidefghi, jklmnopqrabc, abcjklmnopqr, stuvwxyztjbi}

This can also be applied if the words are palindromes

e.g. S = {aba, cdccdc, effefeffe, ghghghhghghg}
S*(6) = {abaaba, cdccdc}
S*(12) = {abaabaabaabc, cdccdccdccdc, abaeffefeffe, effefeffeaba, ghghghhghghg}

If we do have a set with one word of length 12 e.g. S = {abaabaabaaba} we could have a closure containing only words of length 12 or multiples thereof.

Me thinks this might be the solution ...

for the 3rd part of the question though, the question is solely does there exist an S* that has more six-letter words than twelve and based on all the responses, it seems the answer seems to be yes...however this is not the case and the reason is simply one of factors viz. as long as 6 is a factor of 12 (together with 2), S* will always contain more 12-letter words than of the s-letter variety