# Constructing a deterministic finite automaton from a particular regular expression

This is the given question-

Construct a DFA over the alphabet {0,1} such that it accepts all strings containing even number of 0's OR the number of 1's divisible by 3.

The very first problem I've encountered was the 'or' mentioned in the question. Does this mean i just '+' the RegEx for -'accepts all strings containing even number of 0's' and the RegEx for- 'the number of 1's divisible by 3'?

Anyways, this was the approach that I'd tried. I ended up with this RegEx- (1*01*01*)*1* | ((0*10*10*10*)*0*)*

The first part is to check for an even number of 0s and the latter part is to ensure that the number of 1s is divisible by 3. Firstly I'm not sure if this RegEx is right. Let's assume it is-

Now when i try to construct the epsilon-NFA, the conversion took an insane amount of pages and finally when i put it into the converter to convert it into a DFA, it says 'encountered infinite transition loop'.

I dont recall problems of this level being discussed in the class and I'd appreciate any help I can get

Thank you

• (I'd try to construct the automaton directly instead of starting with an RE: How many states does it need to have? How many accepting?) Mar 4 at 7:10
• cs.stackexchange.com/q/45570/755
– D.W.
Mar 4 at 21:51

To check whether the number of $$0$$'s is even we count modulo two. To check divisibility by three of the number of $$1$$'s we need three states. As we have to keep track of these at the same time we have $$2\times 3$$ states.
• Looks OK to me. You can shave off a few symbols if you want: (1*01*0)*1* | (0*10*10*1)*0* Mar 4 at 13:23