2
$\begingroup$

The problem states the following:

Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\{0,1\}$ with overlapping permitted.

I was able to come up "without overlapping" version as follows:

enter image description here

Regex of this DFA is (1+0)*111(1+0)*111(1+0)*111(1+0)*. However this DFA does not accept 11111. This string should be accepted as the problem says overlapping of groups of three consecutive 1's is allowed. But I am not able to guess how do I do this. I feel I cannot do it with DFA as this will require to have some form of memory (for example, once I read 111, it should remember first occurrence of three consecutive 1's is read and also two consecutive 1's of next occurrence have already been read) which is not what DFA provides. Am I right with this?

If not with DFA, can I do this with non deterministic finite automaton (NFA) or deterministic pushdown automaton (DPDA) or non deterministic pushdown automaton (NPDA)? Or this can be done only with Turing machine?

Improve this question
$\endgroup$
1
  • $\begingroup$ Where is the final state? Leftmost bottom? $\endgroup$
    – fade2black
    Commented Oct 1, 2017 at 21:30

4 Answers 4

Reset to default
3
$\begingroup$

No, you don't need NFA (although it is equivalent to DFA) or PDA or Turing machine to solve this problem. It can be easily done with a DFA.

Lets number the states in given DFA in clockwise fashion starting from start state as Q0 to final state as Q9. First of all, it being a DFA, Q9 should have a self loop with label 1 as all possible transitions should be shown from all the states in a DFA.

Now we need to add two states, lets name them Qa and Qb. The changes in the transitions to be made are as follows:-

  1. Instead of having a 1 transition from Q2 to Q3, make a 1 transition from Q2 to Qa.
  2. Instead of having a 1 transition from Q5 to Q6, make a 1 transition from Q5 to Qb.
  3. Make a new 1 transition from Qa to Qb and a 0 transition from Qa to Q3.
  4. Make a new 1 transition from Qb to Q9 and a 0 transition from Qb to Q6.

These changes in the provided DFA will allow it to satisfy given conditions. It simply counts input substring 1111 as two consecutive 111 and skips a step (of three intermediate states), increasing the count be 2.

Improve this answer
$\endgroup$
1
$\begingroup$

I feel I cannot do it with DFA as this will require to have some form of memory.

Why do you feel that a DFA which recognizes 5 1's needs a different kind of memory than one which recognizes three sets of 3 1's each? A DFA has memory (encoded in the state); the limitation is simply that a DFA has only a finite amount of memory. (An NFA is no different.) But in this case, you only need a finite amount of memory. Reading four consecutive 1s puts the automaton in the same state as reading three 1s, some 0s, and another three 1s.

Improve this answer
$\endgroup$
0
$\begingroup$

The problem asks to draw a deterministic finite automaton (DFA), not a pushdown automaton or a Turing machine. If you cannot directly come up with a DFA then you can draw a NFA (or NFA with epsilon moves) and then transform it into a DFA accepting the same language as the NFA. Alternatively, if you can write a regular expression for that language then you could transform it into the corresponding NFA and then DFA. NFA, DFA, and regular expressions represent the same class of languages, namely, regular languages which means once you have a regular expression you can obtain a corresponding DFA or NFA and vice versa.

As for the pushdown automata and Turing machine, you certainly could design a PDA or a TM accepting that language. But remember, PDA and TM computationally are more powerful than FA, meaning that not all languages accepted by a PDA or TM can be accepted by a DFA/NFA, so you cannot always design a PDA or a TM for a language and then transform it into a DFA/NFA accepting that language. However, the opposite is true, every languages accepted by a FA is accepted by a PDA or a TM, but that is another story.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I am guessing what will be smallest regex? Will it be this? : ( (0+1)*111(0+1)*111(0+1)*111(0+1)* |(0+1)*111(0+1)*1111(0+1)* |(0+1)*1111(0+1)*111(0+1)* |(0+1)*11111(0+1)* ) $\endgroup$
    – RajS
    Commented Oct 2, 2017 at 8:00
0
$\begingroup$

Quite a handful... as overlaps are allowed, you need pieces to recognize 111 (one trio), 1111 (two trios) and 11111 (three trios right there, done). Begin by 0s, none or as many as you like. Then the above, jumping off on 0 after the third 1 (to machinery to recognize at least two 111 following the same idea), loop back to the start if 10 or 110. After 1111 jump of to similar machinery to get the last 111.

Improve this answer
$\endgroup$

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.