1
$\begingroup$

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.

$\endgroup$
1
  • 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$ Mar 12, 2020 at 15:53

2 Answers 2

2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Yeah, I think I've got it now. Thank you! $\endgroup$
    – Seth
    Mar 12, 2020 at 14:22
0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Guessing q5 and q6 should be final too. $\endgroup$
    – Seth
    Mar 12, 2020 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, 2020 at 20:21
  • $\begingroup$ So was I. I'm the OP though, so it was more of a feedback. $\endgroup$
    – Seth
    Mar 12, 2020 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, 2020 at 20:40
  • $\begingroup$ Give the states meanings, e.g. "Here we have seen ..." $\endgroup$
    – vonbrand
    Mar 13, 2020 at 1:46

Your Answer

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

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