# What is the regular expression to the given language?

I can't really find out, how can the following given Language be written down with regular expressions

$L = \{ a^{3k-1} b^n a^{2t} \mid n > 0; k, t\ge1 \}$

I had some guesses, but I don't know how to express the part $a^{3k-1}$ of the Language. Probably it should look something like this:

$(aaa)^+$ [something] $b^*(aa^+)$

• possible duplicate of How to prove a language is regular? – D.W. May 10 '14 at 15:37
• The conditions say $n > 0$, so you want $b^+$ instead. – Ryan Smith May 10 '14 at 15:59
• Also, the $(aa^+)$ is not what you want. This matches (for example) $aaa$. – Gene May 10 '14 at 16:13

Look at the three parts of your language:

1. For the $a^{3k-1}$ part, we have possibilities $a^2, a^5, a^8, \dots$. For this part we'll have any 2 $a$s plus a multiple of 3 $a$s. That's expressible as $aa(aaa)^*$.
2. The $b^n$ part is easy, it's just $b^+$, since you need $n>0$.
3. The $a^{2t}$ part is likewise easy. Since $t\ge 1$ we can express this as $(aa)^+$.

Now concatenate these three regular expressions.

Hint: How would you represent the language $L_{odd} = \{ a^n \mid n \,\text{is odd}\}$? First, you'd find an equation that always yields an odd number. The least odd number is $1$. So $a$ is in the language. Now, think of getting new odd numbers from this initial $1$ by adding a number to $1$. You do this by repeatedly adding $2$'s to $1$: $1 + 2k, k \geq 0$, or equivalently $2k -1, k > 0$. In terms of regular expressions, you recognize odd sequences of $a$ by a regular expression that recognizes $a$ and zero or more sequences of $aa$ concatenated to that initial $a$ ($2k, k \geq 0$): $L_{odd} = a(aa)^*$.

It should be possible to generalize to any equation $c_1k - c_2$, $c_1$ and $c_2$ being constants and $c_1k > c_2$, such as the equations $3k-1, n, 2t$, in your case.

Solution:

$aa(aaa)^*b^+(aa)^+$

You need an extra two a's in the beginning to get the right pattern. $(aa)(aaa)^*b^+(aa)^+$