Mathematical Foundation of Computer Science

DHARM

272 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

EXERCISES

10.1 Prove or disprove the regularity of the following languages. (Justify your answer).

(i){0^2 n | n ≥ 1} (ii){1n 0 m 1 n | m and n ≥ 1}

(iii){0n 12 n | n ≥ 1} (iv){0n 1 m | n ≥ m}}

(v){0n 1 n 0 m 1 m | m and n are arbitrary integers}

(vi){w w | w ∈ (0 + 1)^0 }(vii){w wR | w ∈ (0 + 1)+}

(viii){w 1 n wR | n ≥ 1 and w ∈ (0 + 1)+}(ix){0n 1 m | n ≥ m}.

10.2 Decide whether following languages are regular or irregular, (Justify your answer).

(i) The set of odd length strings over {0, 1} in which middle symbol is 0.

(ii) The set of even length strings over {0, 1} in which two middle symbol are same.

(iii) The set of strings over {0, 1} in which the number of 1’s are perfect square.

(iv) The set of palindrome strings of length at least 3.

(v) The set of strings in which number of 0’s and number of 1’s both are divisible by 5.

10.3 Construct minimum state DFA from given FAs shown in Fig. 10.16.

(i)

1 5

3

2

Î Î

a

Î

4

b a

a

(ii)

A BDF

C E

0

1

1

0

0

0

1 1 0 1 1 1

(^00)