Deterministic Finite State Automata in Java

In this post, we will be discussing how to implement a Deterministic Finite State Automata (DFA) Machine in Java which accepts a valid input string with an example.

Deterministic Finite State Automata is a 5-tuple collection. It is a finite state Machine that accepts or rejects a given input String. It has an initial state and a set of final states. A given input string is said to be accepted by a given DFA if and only if starting from the initial state upon scanning the entire input string the machine halts halts in any one of the final states. If it halts in a non-final state, then the string is said to be not accepted by the given DFA.

5-tuples in DFA (Q,∑,δ,q0,F) are :

1. Q represents the set of finite states in the DFA.

2. ∑ represents the input alphabet.

3. δ represents the transition function.

4. q0 represents the initial state.

5. F represents the set of final states.

In this post, let us consider an example i.e... given a Binary input String when read as a decimal number should be divisible by number 4. In general, a DFA can be represented as transition diagram or a transition table.

Let us see transition diagram for the above example.

Now let convert this transition diagram into a transition table.

This transition table is given as input and is represented as an 2-D Character array .Where,

1. First row represents input alphabets.

2. First column represents transition states.

3. The First element is not required and is only just filled with '\$'.

4.The Remaining cells are filled with appropriate transition states as per transition table.

Input:

1. Transition table is given as an input as described above.

2. Initial and Final states are to be  given.

3. And finally the required String is to be given as input.

Output:

A line saying whether the given String is aceepted by given DFA or not.

Note: This code is written in a generic way such that if we change the transition table as per required DFA and change the initial and final states the this code is valid to any DFA.

Inputs are given as follows:

1. transition_table:  2-Dimensional Character array.

`char[][] transition_table = {{'\$', '0', '1'},        {'A', 'A', 'B'},        {'B', 'C', 'D'},        {'C','A','B'},        {'D','C','D'}};`

2. initial_state: A character.

`char initial_state = 'A';`

3. set of final_states: In a HashMap.

`Map<Character, Boolean> final_states=new HashMap<>();final_states.put('A',true);`

4. Input String s: As a String.

`String s = input.nextLine();`

Approach:

1. Take a variable present_state and read the string character by character.

2. Iterate a while loop starting from index=0 to index=s.length()-1.

3. Upon seeing a character, then we go to an another state as per the transition table given.In this way, we will be updating the present_state value.

4. Finally, after reading the total string we reach a state. If we end up in a final state, then the given string is said to be accepted by the given DFA. If we end up in any state other than the set of final_states, then the string is not accepted by the given DFA.

Example:

Input: 1100

Output: The given input Binary String is accepted by the given DFA.

Explanation: Then given input Binary String 1100  when converted as decimal is 12.(12 is divisible by 4).

intial_state-A on seeing first character '1' goes to state B.

B upon seeing second character '1' goes to state D.

D upon seeing third character '0' goes to state C.

Finally, C upon seeing Last character goes to state A.

After scanning the entire string we landed on state A. Since, A is a final state the given String is said to be accepted by the given DFA.

Complexity Analysis:

Let, number of alphabets|∑|=m;

number of finite states|Q|=n;

And, length of the given String = l;

Then,

Time Complexity=O(l*(max(m,n));

This can be reduced to O(l) if we use HashMap to store the transition table;

Space Complexity=O(m*n);

This space is required to the transition table.