computer recursion same question but omitting defdef

Question

Given the alphabet {a,b}, give a recursive definition for the language whose words don't contain the string aa.

My solution is i) b ∈ L1 ii) if w ∈ L1, then so is wba, abw

My question is should i include a in rule i)?

Answer 1

I would go with mutual recursion:

Base cases ($\varepsilon$ as empty string):

$a\in X$

$\varepsilon,b\in Y$

closure conditions:

$w\in X\to wb\in Y$

$w\in Y\to wa\in X\land wb\in Y$

The desired language is then $X\cup Y$.