# How to create a DFA with memory

How can I create a DFA that has memory such that I could write a rule for this DFA that states transition to state B after transitioning from state A at some point (doesn't matter when. Could have been the last state or 5 states ago).

I'm not even sure if creating a DFA like this is possible, hence why I'm asking here. If it's not possible, is there any other state transition algorithm I can use

• I don't understand that rule. Could you elaborate ?
– user16034
Aug 9 at 14:28

By rule, I assume you mean a transition.

You can do this by first replacing the original DFA, $$M$$, with a new one that records whether or not an $$a$$ has ever been read, as follows:

• for each state $$q$$ of $$M$$, it has two states:
• $$q_b$$ ("$$q$$ before $$a$$")
• $$q_a$$ ("$$q$$ after $$a$$")
• for each transition $$(q, c, r)$$ of $$M$$, it has two transitions:
• $$(q_b, c, r_a)$$ if $$c = a$$; $$(q_b, c, r_b)$$ if $$c \not= a$$
• $$(q_a, c, r_a)$$
• its initial state is $$s_b$$
• its final states are $$\cup_{q \in F} \{ q_a,q_b \}$$

Now you can create a transition that only exists for $$q$$ after $$a$$ has been read by creating it for $$q_a$$.

I am confused by some of your terminology. By "DFA table" do you mean the DFA's transition function? Also you want a rule of the form "Accept state $$B$$ after accepting state $$A$$" but an accepting state of a DFA is (basically) a terminating state. Do you mean that $$B$$ should be an accepting state only after visiting $$A$$?

This is doable. All you need to do is create a second, duplicate copy of your DFA. Then $$B$$ in the original is not an accepting state while the copy of $$B$$ is. Finally, the only way to transition from the original to the copy is at state $$A$$ (if you would normally transition to $$C$$ when you receive input $$x$$ while at $$A$$, you now transition to the copy of $$A$$).

• Sorry if I didn't explain properly. When I said "DFA" I meant a table/hashmap/dictionary of all states and their transitions. Also when I said I want "accept state B after accepting state A at some point" what I really meant was "transition to state B after transitioning to state A at some point", the important point is that I don't know when we transitioned to state "A", I just need to remember that at some point we did Aug 8 at 4:44
• @MlLearner just to clarify, we are talking about Deterministic Finite Automata (DFA) right? And if you want to "transition to state $B$ after transitioning to state $A$ at some point" do you mean immediately? If so you can just make that transition, right? If you mean it is only possible to transition to $B$ once you've visited $A$ then the idea in my answer still works. In the copy of the DFA that you start in, there are no transitions to $B$ and in the copy you transition to from $A$, there are transitions to $B$. Aug 8 at 15:10

Though the meaning of "transition to state B after transitioning from state A" is quite unclear, you don't need any special device to memorize if the state A has been reached or not. It suffices to define a set of states from which you can reach A, and another set of states that includes A and such that no transition returns to the first set. What you put in these sets is entirely up to you.