**Problem Detail:**

A language $L$ is defined recursively according to the following rules:

- $λ ∈ L$
- If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$

I am not sure if strings from this language should mix from this definition. Would strings only consist of $bbbb$ and $aaaa$, or can it also consist of $bbaa$, $aabb$, and so on?

###### Asked By : Ducksauce88

###### Answered By : Yuval Filmus

The recursive definition implies that a word $w$ is in $L$ if there is a sequence $w_0,\ldots,w_n=w$ such that $w_0$ is the empty word and for each $i=1,\ldots,n$, either $w_i = bw_{i-1}$ or $w_i = w_{i-1}aa$. This, in turn, implies that $L = b^*(aa)^*$.

Question Source : http://cs.stackexchange.com/questions/43260

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback