Peter Linz Edition 4 Exercise 3.1 Question 18 (Page No. 76)

Question

Find regular expressions for the following languages on {a, b}.

(a) L = {w : |w| mod 3 = 0}

(b) L = {w : na (w)mod 3 = 0}

(c) L = {w : na (w)mod 5 > 0}

Also Design DFA for the same.

Comments

........

---

.........

Answer 1

............

For option b

R.E =( b*ab*ab*ab*)* +b*

 

Answer 2

(a) $[(a + b)(a + b)(a + b)]^*$

(b) $(b^*ab^*ab^*ab^*)^* + b^*$

or, $(b^*ab^*ab^*ab^*)^*.b^* $

(c) $[(b^*ab^*ab^*ab^*ab^*ab^*)^* + b^*](ab^* + ab^*ab^* + ab^*ab^*ab^* + ab^*ab^*ab^*ab^*)$

or, $(b^*a+b^*ab^*a+b^*ab^*ab^*a+b^*ab^*ab^*ab^*a)[(b^*ab^*ab^*ab^*ab^*ab^*)^* + b^*]$

Comments

Yea I wrote the r.e. in a hurry and forgot about it :p

I've edited my answer, you can check now.

---

@pradeep, first design the r.e. for na(w) mod 5 = 0. Then if you allow one extra 'a' either in the front or the back (doesnt matter), then the r.e. will get adjusted to na(w)mod 5 = 1. So you can write the r.e. for mod 5 > 0 i.e. mod 5 = 1, mod 5 = 2... mod 5 = 4 ;and finally add them up, and you'll land up with the same r.e. i've written.

---

Hey,

Can you please check whether my R.E is correct?