Proof for recursively defined sets Language $L\subset \{a,b\}^*$ is such that:


*

*$\epsilon \in L$

*$a \in L$

*For any $x\in L$, $xb\in L$ and $xba\in L$

*Nothing else in $L$.


Im just learning recursive sets, but with that definition am I correct that:
$\epsilon \in L$ so:
$b\in L$ and $ba\in L$,
$bb\in L$ and $baba\in L$,
$bbb\in L$ and $bababa\in L$
...
$a \in L$ so:
$ab\in L$ and $aba\in L$,
$abb\in L$ and $ababa\in L$,
$abbb\in L$ and $abababa\in L$
...
I need to prove that $L$ is the language of all strings not containing the substring $aa$.
How do I begin proving this? I've used induction on other recursively defined sets but I cant figure out how to use it here. 
 A: Point 4 means your language is the "smallest" language verifying rules 1 to 3. "Smallest" actually means the intersection of all such languages:
$$L^\star=\cap_{L\text{ verifying rules 1 to 3}} L$$
Let $L_{no\ aa}$ be the language of words not containing any 'aa'. This is not a precise definition but can be made into one by translating it into the condition: $\forall w\in L_{no\ aa}$, ($w_i=a\text{ and }i<|w| \implies w_{i+1}\neq a)$. A few basic properties have to be proved on $L_{no\ aa}$ before the following proof is made.
$L_{no\ aa}$ is one such language so it contains the desired language: $L^*\subset L_{no\ aa}$ (actually some properties have to be proved first on $L_{no\ aa}$).
You just have to prove that it is the smallest, which means a correct language contains any word without 'aa': $L_{no\ aa}\subset L^*$. This can be proved by recursion on the length of the word:


*

*all words of length $0$ not containing $aa$ belong to $L^*$: it is true from rule 1.

*all words of length $1$ not containing $aa$ belong to $L^*$: it is true from rule 2 and 3.

*if the property is true for words of length less than $n$, let $w$ be a word of length $n+1$ without 'aa'. Either $w=w'b$ or $w'ba$. In both cases $w'$ does not contain 'aa' (again a little bit of work is needed to get a formal proof) and you can conclude from 3 and the recursion hypothesis. 
