0
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ I don't understand that rule. Could you elaborate ? $\endgroup$
    – user16034
    Aug 9 at 14:28

3 Answers 3

Reset to default
0
$\begingroup$

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

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

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – MlLearner
    Aug 8 at 4:44
  • $\begingroup$ @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$. $\endgroup$
    – NaturalLogZ
    Aug 8 at 15:10
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.