1
$\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?

$\endgroup$
  • $\begingroup$ Where is the final state? Leftmost bottom? $\endgroup$ – fade2black Oct 1 '17 at 21:30
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.

$\endgroup$
1
$\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.

$\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.

$\endgroup$
  • $\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$ – anir Oct 2 '17 at 8:00

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.