Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 249

9.2 Write regular expressions for each of the following languages over the alphabet {a, b}.

(i) All strings that don’t have substring ba.

(ii) All strings that don’t have substring aab and baa.

(iii) All strings that have even number of a’s and odd number of b’s.

(iv) All strings in which a’s or b’s is doubled but not both.

(v) All strings in which symbol b is never tripled.

(vi) All strings in which number of a’s are divisible by 5.

9.3 Construct the FA for the following regular expressions.

(i)(11 + 0)* 0* (00 + 1)*

(ii)01((10* + 11) + 0)*

(iii)((0 + 1) (0 + 1))* + 11 + 0(1 + 0)* + ∈∈∈∈∈

9.4 Construct the regular expression for the following DFA, shown in Fig. 9.45.

1

2

3

a

b

b

b

a a

Fig. 9.45

9.5 Describe the language denoted by the following regular expressions

(i)((b + aa)*)* (ii)(b (a + bb)*)*

(iii)(b (abb)* a (baa)*)* (iv)(a + b) a (ab)*

(v)(a*b*)*

9.6 Prove are disprove the following for regular expressions

(i)(a*b*)* = (a + b)* (ii)(a + b)* = a* + b*

(iii)(a + b)* a (a + b)* b (a + b)* = (a + b)* ab (a + b)*

(iv)(a + b)* ab (a + b)* + b*a* = (a + b)* (v)(aa*1)*1 = 1 + a (a + 1a)*11

9.7 Construct the regular expression corresponding to the followng FAs shown in Fig. 9.46.

0

1

0, 1 0, 1

()a ()b

0

1

0, 1

0, 1

()c

0

0, 1

0, 1

()d

1

0, 1