CODEWITHSUNDEEP
state-machineautomatadfa
Kaushik Roy Chowdhury
Kaushik Roy Chowdhury

Reputation: 19

Construct a DFA which accept the language L = {w | w ∈ {a,b}* and Na(w) mod 3 > Nb (w) mod 3}

I cannot solve this problem , if anyone can solve this problem.

Construct a DFA which accept the language L = {w | w ∈ {a,b}* and Na(w) mod 3 > Nb (w) mod 3}

Upvotes: 0

Views: 1021

Answers (1)

Patrick87
Patrick87

Reputation: 28332

Make a DFA with nine states named q00, q01, q02, q10, q11, q12, q20, q21 and q22. Each state qxy will correspond to a pair (x, y) = (Na(w) mod 3, Nb(w) mod 3). Then, simply make the accepting states the ones where Na(w) mod 3 > Nb(w) mod 3 is true: q10, q20 and q21. You can lay these states out in a 3-by-3 grid and have the Na(w) component move horizontally along rows and the Nb(w) component move vertically down columns. These will need wrap-around in both columns and rows.

Upvotes: 1

Related Questions