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

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

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

$$\{0,1\}^*\cdot1\cdot\{\{0,1\}\cdot\{0,1\}\cdot0\}^*$$

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

Edit:

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.

• $\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. – Matthew Daly Dec 2 at 22:54
• Have you tried creating a NFA (nondeterministic) for your reversed regular expression? You could then convert the NFA to a DFA. – James E. Reid Dec 3 at 3:51
• The minimal DFA for $L_2$ has 8 states, which is still manageable by hand. Just use the approach suggested by @james-e-reid . – J.-E. Pin Dec 3 at 8:03