Find Regular Expressions for the following languages L3 w N

Find Regular Expressions for the following languages. L_3 = {w: Na(w) mod 3 > 1} sigma = {a, b, c} L_4 = {all strings that do not begin with \"aa\"} sigma = {a, b}

Solution

1. We need to have words in language L where number of a % 3 is greater than 1.

However, anything mod 3 can be either 0, 1 or 2. So, questions is asking for elements where a\'s length is 3*x+2, x can be 0 to infinity.

Hence, reg exp can be:

((b+c)*+a(b+c)*a(b+c)*a)* a (b+c)* a (b+c)*

2. String which does not begin with aa can begin with either ab, ba or bb.

Hence, re can be:

(ab)(a+b)* + (b)(a+b)*