Answer to Question #221003 in Algorithms for Fareeha Nadeem

Question

Q2: Build a DFA for each of the following languages:

1)     {w ∈ {a, b}* : every ‘a’ in ‘w’ is immediately preceded and followed by ‘b’}

2)     {w ∈ {a, b}* : ‘w’ does not end in ‘ba’}

3)     {w ∈ {0, 1}* : ‘w’ corresponds to the binary encoding, (without leading 0’s,) of natural numbers that are evenly divisible by 4}.

4)     {w ∈ {a, b}* : ‘w’ has both ‘aa’ and ‘bb’ as substrings}.

5)     {w ∈ {0, 1}* : ‘w’ has odd number of 0’s and 1’s}.

Answer 1

The regular expression for the given terms is -

$(b \cup bab)*$

$\in \cup a \cup (a \cup b)* (b \cup aa)$

$(1(0 \cup 1)* 00) \cup 0$

$(a \cup b)* aa (a \cup b)* bb (a \cup b)* \cup (a \cup b)* bb (a \cup b)* aa (a \cup b)*$