Consider the following recursive definition for $L ⊆ \{a, b\}^* : b ∈ L; ∀w ∈ L, bw, wa \text{ and } aw$ are in $L$. Give a non-recursive definition for L (using Kleene star or in English)
I'm trying to answer this problem, but I'm struggling finding the good answer using the Kleen star
Can someone explain me?
The definition tells you that every word in $L$ can be formed by starting with $b$ and repeatedly adding an $a$ or a $b$ at the beginning or an $a$ at the end. For instance, the derivation
$$\color{red}b\overset{bw}\longrightarrow b\color{red}b\overset{aw}\longrightarrow ab\color{red}b\overset{bw}\longrightarrow bab\color{red}b\overset{wa}\longrightarrow bab\color{red}ba\overset{aw}\longrightarrow abab\color{red}ba\overset{wa}\longrightarrow abab\color{red}baa$$
shows a derivation of the word $ababbaa\in L$; above each arrow I’ve indicated which rule I’m using for that step. I’ve also colored the initial $\color{red}b$ red.
By looking at some examples and thinking about the rules for constructing members of $L$ you should be able to answer these two questions, and when you’ve done that, you’ve essentially described which words are in $L$. Once you can describe $L$ in words, we can help you describe $L$ symbolically with the aid of the Kleene star.