3

Language $L\subset \{a,b\}^*$ is such that:

  1. $\epsilon \in L$
  2. $a \in L$
  3. For any $x\in L$, $xb\in L$ and $xba\in L$
  4. 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.

Clive Newstead
  • 64,925
Deniz Cetinalp
  • 829

1 Answers1

2

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.

omangin
  • 71