# Kleene Star & proof regarding Alphabets

I am looking for some hints or suggestions on my answers for Q1 and Q2 I think i am near correct but with help I could understand what i'm doing wrong.

Q1: Given the alphabets {00,11} and {0,1}.

1. Show five shortest elements from {00,11}*
2. Are there strings in {00,11}* of odd length?
3. Are there any strings w in {00,11}* of length 3 such that w=w^R?

4.What is the intersection of {0,1}* and {00,11}*?

1. ϵ, 00, 11, 0011, 1100

2. Yes 0000 is a string of odd length, length 3

3. Yes, suppose w is a string then w = 0000 is a string of length 3 and w$^{R}$ = 0000

4. {0,1}$^{*}$ $∩$ {00,11}$^{*}$ $=$ strings that are members of both sets

Since the strings get repeated for every length i think all elements are members of both sets because this is a infinite set so the length can increase forever.

Q2: Let A be an alphabet. By A** let us denote the set of all strings from A* of even length.

Show that

(AA)* = (A*)*

I believe I need to show two cases, not sure if i proved the cases exactly correct.

1. (AA)$^{*}$ $⊆$ (A$^{*}$)$^{*}$
2. (A$^{*}$)$^{*}$ $⊆$ (AA)$^{*}$

case 1: Suppose w $∈$ (AA)$^{*}$ then by definition of kleene star w will contain 0 or more strings of AA which means w can be a string from A* since A* just repeats the string with a longer length and concatenation with two strings from AA is the same as a string repeated with longer length so

w $∈$ (A$^{*}$)$^{*}$

$=>$ (AA)$^{*}$ $⊆$ (A$^{*}$)$^{*}$

case 2: Suppose w $∈$ (A$^{*}$)$^{*}$ then w is a 0 or more strings from the alphabet A and adding another kleene star would make more combinations of the strings from A with higher length which is the same as concatenating two strings to equal the same length so

w $∈$ (A$^{*}$)$^{*}$

$=>$ (A$^{*}$)$^{*}$ $⊆$ (AA)$^{*}$

• The five shortest are the "null" (length $0$) word, $99$, $11$, $0011$, and $1100$. – André Nicolas Jan 15 '15 at 1:49
• So ϵ,00, 11, 0011, 1100 then – geforce Jan 15 '15 at 1:52
• Yes, that's right. And since the "basic" words have an even number of bits, all words in the Kleene star have an even number of bits. In principle this should be done by induction, but there is a good case to be made that it is obvious. – André Nicolas Jan 15 '15 at 1:55

these are my answers: Question 1

1. 00,11,0011,1100, ϵ
2. no string of odd length can be made over alphabet A.
3. 001100, 110011, 000000,111111 (00 and 11 are each considered to be one character)
4. {00,11}^*
• Ok thats wat I was wondering about on q3 I didn't know what kind length they were talking about. So every repeat of 00 or 11 increases length by 1. Also why is q4 {00,11}^* the answer for that question? Is it because the kleene star operation is infinite so the string length will repeat 00 , 11, so it will always be equal? But 0 and 1 at length 1 is not part of {00,11}^*? – geforce Jan 15 '15 at 22:15
• its because every string in {00,11}^* consists of 0s and 1s and hence it belongs to the set of all strings {0,1}.. to {0,1}^* – ars Jan 15 '15 at 22:21

A string has a length; the string 01001 has length 5. A string $S$ is said to be "shorter" than a string $T$ if the length of $S$ is less than the length of $T$.

1. The five shortest elements of $\{00, 11\}^*$ are not what you said; you included 10, but that is not an element of $\{00, 11\}^*$.

2. The string $\epsilon$ has length 0, not length 1. $\epsilon$ is the string with no symbols.

3. You have this right.

4. I think your answer to this, while true, will probably not get a good mark. (It's like that joke where the customer asks the waiter "What's the soup du jour?" and the waiter replies "Oh, that's the soup of the day.") I guess the question is not asking for a definition of what it means to be in the intersection; rather, it wants you to describe which strings are in the intesection, by giving a simple property common to all those strings. Then you said "all elements are members of both sets". All elements of what?

For Q2, are you sure you have the question right? It seems to define a notation $A^{**}$ but then the question you reported doesn't use that notation. That is surprising.

• For Q2 i stated "By A** let us denote the set of all strings from A* of even length" so that is ( A* )* ? – geforce Jan 15 '15 at 1:53
• Also i think i did Q1 3) wrong because 0000 is length 2 not length 3? – geforce Jan 15 '15 at 1:57
• From your statement in Q1 2) that contradicts at least one thing you said because if that is true then 3) is wrong – geforce Jan 15 '15 at 2:00
• Is "By A** let us denote the set of all strings from A* of even length" part of the question, or is it part of your answer? – MJD Jan 15 '15 at 2:02
• Well $(AA)^*$ is not equal to $(A^*)^*$, but it is equal to $A^{**}$, so either you reported the question incorrectly or the person who wrote the homework made a mistake. – MJD Jan 15 '15 at 18:27