1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ (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?) $\endgroup$
    – greybeard
    Mar 4 at 7:10
  • $\begingroup$ cs.stackexchange.com/q/45570/755 $\endgroup$
    – D.W. ♦
    Mar 4 at 21:51

1 Answer 1

Reset to default
1
$\begingroup$

It is a detour to construct the automaton by first determining a regular expression. The description of the languages gives enough information to obtain possible states for the automaton.

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you for your answer. Is my RegEx correct though? $\endgroup$
    – MrKhonsu
    Mar 4 at 5:05
  • $\begingroup$ Looks OK to me. You can shave off a few symbols if you want: (1*01*0)*1* | (0*10*10*1)*0* $\endgroup$
    – Hendrik Jan
    Mar 4 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.