2
$\begingroup$

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^+)$

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

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.

$\endgroup$
1
$\begingroup$

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)^+$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.