recursive definition odd length strings

Given the alphabet {aaa bbb}, give a recursive definition for the language that only contains odd length strings. must be constructive definition we are suppose to treat aaa as one letter and bbb as one letter

this is what I have so far, but I feel that I am missing something

We will represent our language with L
Rule#1: aaa,bbb is in L
Rule#2: if w is in L, then so are
(i): waaaw
(ii): wbbbw


thanks

• The string $aaa aaa bbb$ does not seem to be reached by your rules. Aug 27, 2014 at 15:36
• so would I have to add rules that say wwa and wwb as well. I am still pretty confused Aug 27, 2014 at 16:44
• Or would I just have (i): www and delete the (ii) Aug 27, 2014 at 17:41
• Why on earth do you call them aaa and bbb? What's wrong with a and b? Aug 28, 2014 at 8:24

Here's a hint.

You see that $aaa$ and $bbb$ are in $L$.

You also see that one way to guarantee that you have an odd-length string is to combine three odd-length strings.

Given just your two starting strings above, what is the next-largest string length you can create? How can you combine your two starting strings to cover your choices? Can you generalize this?

• the next largest string would be aaa aaa aaa so do you mean I should just have one rule that says www Aug 27, 2014 at 16:46
• Ha ... I made a small mistake in my hint. You're on the right track, though. Your rule $www$ accounts for $aaa aaa aaa$ and $bbb bbb bbb$ to start out, but what about $aaa bbb bbb$? Or $bbb aaa bbb$?
– John
Aug 27, 2014 at 17:47
• so is it three rules www, waaaw and wbbbw or would it be more than that like this www,waaaw,wbbbw,wwaaa,wwbbb,aaaww,bbbww I am still confused Aug 27, 2014 at 17:57
• I'd think if you had two words $w_1, w_2$ in $L$, then $w_1w_1w_1$, $w_2w_1w_1$, $w_1w_2w_1$, and $w_1w_1w_2$ would also be words, and it would cover all possible nine-letter words you could make, right?
– John
Aug 27, 2014 at 18:03
• I am sorry, but I am still confused you mean do www,aaaww,waaaw,wwaaa and this would cover all of them? but what about bbb Aug 27, 2014 at 18:17

Try to think about how new words can be reached from shorter ones. Hint: The length has to be odd, so it would be helpful to increase lengths by two in each step. Now, how can you assure you get all words of length n+2 if you already have the words of length n in your language. (It is a bit like formal induction, i.e. base case aaa and bbb which you already have and then the inductive step going from n to n+2.)

It looks like your language is $$(\{aaa, bbb\}\{aaa, bbb\})^*\{aaa, bbb\} = \{aaaaaa, aaabbb, bbbaaa, bbbbbb\}^*\{aaa, bbb\}.$$ It is a regular language, so you can find a finite automaton or a regular grammar to describe it.

We will represent our language with L
Rule#1: $aaa,bbb$ is in $L$ Rule#2: if $w$ is in $L$, then so are

(i): $waaaaaa$

(ii): $wbbbbbb$

(iii):$waaabbb$

(iV):$wbbbaaa$

All possible strings having odd length can be made with these two rules.