Search code examples
javafinite-automatacomputation-theorydfa

how do i represent transitions when writing a code for a dynamic DFA?

I want to write a java program to build a dynamic finite automata for any language with any alphabet and then test the machine to accept or reject any given word.

i entered the the states number, alphabet, start state and final state(s), but stopped at writing the transitions which are what a finite automata is mostly about.

Solution

  • This is a nice project. As you are saying, you need first to carefully define an input language to describe any FA. In addition to what you already have, you'll need state transitions. This is typically done in one of two ways:

    1. A full transition table.
    2. A description of a transition graph, where missing edges are interpreted as a transition to a "crash." I.e a transition to a "black hole" state, a non-accepting state with a self-loop for all characters of the language.

    Form 1 is simpler to read, but far less convenient because you must explicitly specify all transitions. Form 2 is more convenient. I recommend form 2. A DFA description with this form might look like this:

    4  # There are 4 explicit states (plus a 5th for the "black hole")
   # Assume they have state numbers 0 (the start state), 1, 2, 3.
ab # A string of characters in the FSM alphabet
1 3 # Numbers of accepting states.
5 # Number of explicit state transitions
0 1 a # From 0 to 1 on input a
1 1 a # From 1 to 1 on input a
1 2 b # From 1 to 2 on input b
2 3 a # From 2 to 3 on input a
3 3 a # From 3 to 3 on input a

    You can certainly come up with fancier languages, but this one is sufficient and simple to parse.

    Note that a fully specified DFA with 4 states and 2 input characters has 2(4)(4-1) = 24 transitions, and we've only given 5 of them in this machine. To fill in the remaining ones, add a "black hole" state 4. This has a self-loop on all characters. For each node i where an outgoing transition on some character c is missing, add a transition i 4 c to complete the DFA.

    To represent a DFA in Java, a good choice is a Map<Integer, Map<Character, Integer>>. The first map key is a state number. The second is the input character. The final value is another state number. So if you're currently in state s and the input character is c, you'll get the next state with something like

    nextState = transitionMap.get(s).get(c)

    Note that there's no need to explicitly add state 4 or all the transitions to it. Rather, when evaluating the expression above, just cause the machine to reject any time nextState turns out to be null.