CODEWITHSUNDEEP
dfa
Tommy K
Tommy K

Reputation: 1807

Deterministic Finite Automata state diagram

I need to make an 8-state DFA that takes 0s and 1s and has an even number of 1s and a substring of ...000... somewhere in it. So I know how to find a substring of 000 and I know how to find an even number of 1s, but I'm not sure how to put this together. Is there like a formula or something to follow for this, I just started DFAs and NFAs so I'm not quite sure how to solve this besides drawing it out with trial and error. Any help would be great

Upvotes: 0

Views: 361

Answers (1)

Gerard Rozsavolgyi
Gerard Rozsavolgyi

Reputation: 5074

For the testing even number of ones:

enter image description here

Then for testing the 000 substring:

enter image description here

Then we can compute the intersection of these DFA using the classical cross-product construction and get the (minimal) DFA:

enter image description here

Upvotes: 1

Related Questions