Inductively define language a, b, aa, bb, aaa, bbb, ....

[Astr00]

[Thread moved by mentor]

Hi there.

As the title says, I want to inductively define the language consisting of the strings {a, b, aa, bb, aaa, bbb} and so on. I have come up with the following:

Let S be the smallest set so that a, b ∈ S and if x, y ∈ S, then xa, yb ∈ S.

Is this a correct method of inductively definining such a language, and am I defining the language that I set out to do?
If it is, could I also accomplish the same with just the empty string as my base set?
An example of that would be:

Let S be the smallest set so that Λ ∈ S and if x, y ∈ S, then xa, yb ∈ S.

In this case I think Λ would act as both the x and y, which would turn into Λa, Λb or just a, b in the next step. But is this a correct way of doing it?

Edit: I should have read the rules before posting. Could a moderator move this to the homework forum?

 

[andrewkirk]

The set you have defined would include ba and ab, so is larger than your target set. You need to make the second part of your criterion ensure that an a can only be added to a string of 'a's, and likewise for 'b's.

It will help to have a notation to refer to a string of repeated letters. Why not use $x^n$ (or x^n if you don't know latex) to denote the letter denoted by x, repeated n times?