Are those recursive definitions true?

Question

I am trying to construct languages.

Let Σ = {a, b}

Let's say in this language BB, every word has to have the substring bb.

So the recursive definition is:

Rule 1    bb is in the BB 
Rule 2    If x is in BB, then so is x + bb
Rule 3   If x is in BB, then so is bb + x.
Rule 4    The only elements in the set BB are those that can be produced from the three rules above.    

Let say, I have another language called NOTBB. In this language every word should not have the substring bb

Rule 1 a and b are in NOTBB
Rule 2 If x is in NOTBB, then so is x + a
Rule 3 If x is in NOTBB, then so is x + ab
Rule 4    The only elements in the set BB are those that can be produced from the three rules above.

The definitions are correct, right?

Answer 1

The first one is not correct: "abb" should be in BB, since it has "bb" as a substring, but cannot be derived from the rules given.

The second one is correct, though.

Answer 2

Your first definition does not describe the intended set. To build a string according to your definition, you must start with "bb" and attach more "bb"s - so the strings included are just bb, bbbb, bbbbbb, and so on. "bbb", for example, is not in the set, because to be included by rules 2 or 3 it would have to come from "b", which can't be the set because it doesn't have a "bb" in it.

What you want to say is that if x is in BB, then x + a, x + b, a + x, and b + x are all in BB - notice that adding a symbol to one end can't destroy the "bb" substring that was already present.

EDIT: (To address a comment below) Your fourth rule states that the only way to get a string in BB is to build it using (1)-(3). That means that if a string is going to be in BB, it must be forced to be in BB by one of those three rules. (2) and (3) don't say anything about what happens if the string you start from isn't in BB; so getting, for example, "abb" from "a" isn't an application of either rule, because those rules don't say that x + bb is in BB when x = a.

In your comment, you distinguished between "pick x from BB" and "if x is in BB". There is no difference between those. In the first, you always get something in BB; in the second, you might get something not in BB, but if you do you don't do anything with it. To take an analogy, suppose I gave you two instructions: first, "pick an apple from the store and give it to me". Second, "get something from the store, and if it's an apple, give it to me". In neither situation will you ever give me something that isn't an apple - it's just that in the second case you sometimes waste your trip to the store.