[Solved]: regular expression given the language

Problem Detail: 

The language is: $$ L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \} $$

My attempt at an answer: $$ (a \cup b)^{3k} $$

This will work if the a OR b can change for each instance in the string that is (3k) long. If not, what can I do to fix this?

Asked By : pachun

Answered By : Patrick87

First off, putting $k$ in the regular expression is not allowed by typical regular expression syntax, unless I'm mistaken. Even adding constant powers is a shorthand notation, not a part of the regular expression formalism. Even if it were possible, using that notation, you could mix $a$s with $b$s, so that not all $a$'s would necessarily come before all $b$s ... so that's not the right direction.

You want strings that begin with $a$s, end with $b$s, and have a total length that is divisible by three. There are a few ways you could go about this. Since you want a regular expression, we might try to develop one directly, without going through a finite automaton.

For a string $x$ from $a^*b^*$ to be in your language, its length must be divisible by three. In other words, it must be true that $|x| = 3k$. Let $x = yz$, where $y \in a^*$ and $z \in b^*$. Then $|x| = |y| + |z|$. So we must have that $|y| + |z| = 3k$. There are only a finite number of ways in which this can happen:

1. $|y| = 3k_1$ and $|z| = 3k_2$, or
2. $|y| = 3k_1 + 1$ and $|z| = 3k_2 + 2$, or
3. $|y| = 3k_1 + 2$ and $|z| = 3k_2 + 1$.

Suppose you can create regular expressions $r_1, r_2, r_3$ corresponding to those three cases. Then you can find the regular expression for your language by taking the union. Let's see how that would work for each case.

1. This case is easy: the number of $a$'s is divisible by 3, and so is the number of $b$'s. We get a regular expression $r_1 = (aaa)^*(bbb)^*$.
2. Based on the previous answer, this isn't so bad, either: $r_2 = (aaa)^*a(bbb)^*bb$.
3. Finally, $r_3 = (aaa)^*aa(bbb)^*b$.

We get an easy regular expression by taking the union of these (I use $+$, but $\cup$ is sometimes also used): $r = r_1 + r_2 + r_3 = (aaa)^*(bbb)^* + (aaa)^*a(bbb)^*bb + (aaa)^*aa(bbb)^*b$.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents