Regular expression for a context free language

Question

this is the context free language I've been given:

$S\rightarrow aSTb\\ S\rightarrow b\\ T\rightarrow Ta\\ T\rightarrow \lambda $

And I want to figure out what language it represents and write the regular expression for it, including conditions that define it. So far I've come up with the following:

$L=\{w\in(aa^*b)^*a^*b| \#_b(w)\leq1+\#_a(w) \}$

where $\#_b(w)$ means the number of b's in the word.

The condition itself seems to be correct, at least for all the examples I tried. However, some words can be created with the expression I wrote but do not belong to the language. For example "aaaaabb"

I'd appreciate any help with this. Thank you

Answer 1

Expression $a^nb(a^{k_1}ba^{k_2}b\ldots a^{k_n}b)^n$ with $n\geq 1$, $k_1,\ldots,k_n\geq 1$.

Answer 2

The language has derivations of the form $S\rightarrow aSTb\rightarrow aaSTTb\rightarrow^* a^nST^nb\rightarrow^* a^nba^nb$. All derivations are of this kind. So the language is context-free, but not regular. Use the pumping lemma to show this. Hence, there is no regular expression describing this language.

Answer 3

The language is indeed context-free and not regular. An expression for it can be obtained by solving the system of equations \begin{align} S &= aSTb + b \\ T &= Ta + 1 \end{align} The second equation gives immediately $T = a^*$ and thus the first equation becomes $S = aSa^*b + b$. If follows that the language can be written as $$ L = \bigcup_{n \geqslant 0} a^nb(a^*b)^n $$

P.S. I use $1$ instead of $\lambda$ for the empty word.