I need to create a deterministic finite automata whose language consists of words over $\{0,1\}$ of any length, satisfying the following constraint:

Among any subsequent 3 numbers, there needs to be exactly two 1s, and exactly one 0.

I've spent a couple hours studying DFAs, but I can only find solutions like the one I need to one of these issues. Meaning that among the 3, there can be at most 1 of something, or there needs to be at least 2 of something. I'm pretty much lost in how I'm supposed to combine these into a single DFA.

  • 1
    $\begingroup$ I'm pretty much lost in how I'm supposed to combine these into a single DFA. You can use the product construction. $\endgroup$ – Yuval Filmus Mar 12 at 15:53

Imagine writing a program on any high-level language for checking if string corresponds the given restriction. You would probably iterate symbols one by one and check if appending next symbol breaks the restriction.

Now note that you need only two last symbols to do it, and there are finite number of two-symbols combinations (namely $--, -0,-1,00,01,10,11$, where "$-$" stands for absence of preceding symbol at the very beginning of the string).

Why wouldn't we use these combinations as automata states? You are left only to add transitions, which are pretty straightforward (e.g. appending $0$ to $11$ transits to $10$, appending $1$ to $00$ transits to the dead state, and so on). Can you finish it now?

| cite | improve this answer | |
  • $\begingroup$ Yeah, I think I've got it now. Thank you! $\endgroup$ – Seth Mar 12 at 14:22

This is what I've come up with. Not sure if it's correct though. enter image description here

| cite | improve this answer | |
  • $\begingroup$ Guessing q5 and q6 should be final too. $\endgroup$ – Seth Mar 12 at 18:22
  • $\begingroup$ We're not really looking for answers that consist solely of a picture or a bunch of code. Instead, we're looking for answers that come with an explanation (of where you got this answer and why it is correct), justification, and/or rationale. $\endgroup$ – D.W. Mar 12 at 20:21
  • $\begingroup$ So was I. I'm the OP though, so it was more of a feedback. $\endgroup$ – Seth Mar 12 at 20:35
  • $\begingroup$ I see your point though. It is annoying to look through a bunch of code written by someone else. $\endgroup$ – Seth Mar 12 at 20:40
  • $\begingroup$ Give the states meanings, e.g. "Here we have seen ..." $\endgroup$ – vonbrand Mar 13 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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