Question #221003

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}.


1
Expert's answer
2021-07-29T03:13:39-0400

The regular expression for the given terms is -

(bbab)(b \cup bab)*

a(ab)(baa)\in \cup a \cup (a \cup b)* (b \cup aa)

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

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


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS