$$\mathcal{L}_1 = \{\text{Strings with a 1 at a multiple of 3 from the front}\} $$ and $$\mathcal{L}_2 = \{\text{Strings with a 1 at a multiple of 3 from the end}\}$$

I need to design a DFA for these.

for $\mathcal{L}_1 $ I found the regular expression $\{0\cdot \{0,1\}\cdot\{0,1\}\}^*\cdot1\cdot\{0,1\}^*$

Since if the string starts with a 1 then it doesn't have to have another 1. It is already in the set of accepted strings ($0$th position is a multiple of $3$).

Then I have the dfa: enter image description here

for $\mathcal{L}_2$ I just reversed the regular expression for $\mathcal{L}_1$:


But I am unable to come up with a DFA to accept this regular expression, which is odd.


So you would basically solve the language: {1 at a distance 3k and the total length is 3k +1 OR 1 at a distance 3k + 1 and the total length is 3k + 2 OR 1 at a distance 3k+2 and the total length is 3k} which is straightforward but a very large DFA: At most $12^3 = 1728$ states.

  • 1
    $\begingroup$ $\mathcal{L}_1$ can terminate whenever you like once it meets the criteria. $\mathcal{L}_2$ can only terminate every three spots after a 1. Worse yet, you don't know "which 1" is the one that the one that will be a multiple of 3 from the end. You will need a far more complex DFA to keep track of which states can be end states. $\endgroup$ – Matthew Daly Dec 2 at 22:54
  • 1
    $\begingroup$ Have you tried creating a NFA (nondeterministic) for your reversed regular expression? You could then convert the NFA to a DFA. $\endgroup$ – James E. Reid Dec 3 at 3:51
  • $\begingroup$ The minimal DFA for $L_2$ has 8 states, which is still manageable by hand. Just use the approach suggested by @james-e-reid . $\endgroup$ – J.-E. Pin Dec 3 at 8:03

Your Answer

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

Browse other questions tagged or ask your own question.