0
$\begingroup$

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

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

4 Answers 4

2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ the next largest string would be aaa aaa aaa so do you mean I should just have one rule that says www $\endgroup$
    – tommycatpr
    Aug 27, 2014 at 16:46
  • $\begingroup$ 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$? $\endgroup$
    – John
    Aug 27, 2014 at 17:47
  • $\begingroup$ 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 $\endgroup$
    – tommycatpr
    Aug 27, 2014 at 17:57
  • 1
    $\begingroup$ 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? $\endgroup$
    – John
    Aug 27, 2014 at 18:03
  • $\begingroup$ 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 $\endgroup$
    – tommycatpr
    Aug 27, 2014 at 18:17
1
$\begingroup$

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.)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .