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