Step-1 : Prompt the user for the number of states, number of input symbols, initial and final states and the transition table of NFA.
Step-2 : The initial state and the input symbols in the resultant DFA will be the same as it is in the given NFA.
Step-3 : Push the initial state into a queue.
Step-4 : Store the front element of the queue in a variable and pop that element from the queue.
Step-5 : If the element is already visited then go to Step-9.
Step-6 : For each state in the element, apply the input and find out the resultant transition states. Combine the obtained set of states and take it as a new state in DFA. Store this transition in the transition table of DFA.
Step-7 : Push the obtained set of states into the queue.
Step-8 : Repeat Step-6 and Step-7 for all the input symbols.
Step-9 : If the queue is not empty then go to Step-4.
Step-10 : If one of the states in any combined state is final state then mark that combined state as a final state.
Step-11 : Display the transition table of the resultant DFA along with its initial and final states.
2 . NFA WITH EPSILON MOVES TO NFA
Algorithm:
Step-1 : Prompt the user for the number of states, number of input symbols, initial and final states and the transition table of the NFA with epsilon moves.
Step-2 : Find epsilon closure of each states given and store it in a variable.
Step-3 : For each given state and for each given input find its transition in NFA without epsilon moves using the below formula.
Transition_In_NFA_Without_Epsilon_Moves(q,a)=
epsilon closure(TransitionInNFAWithEpsilonMoves(epsilon closure(q), a))
Step-4 : The number of states, the states and the initial state will be the same.
Step-5 : The Input Symbols will also be the same excluding the epsilon.
Step-6 : If the epsilon closure of a state contains a final state then mark that state as a final state.
Step-7 : Display the transition table of NFA and display the initial and final states of it.
3 . MINIMIZATION OF DFA
Algorithm:
Step-1 : Prompt the number of state(say n), number of input symbols, the initial and the final states and the transition table of the DFA.
Step-2 : Create a boolean table of size n*n and initialise all the values as true. This table is used to identify whether two states are equivalent or not.
Step-3 : Traverse the table, if one state is a final state and other state is a non final state then mark their combination as distinguishable by storing false in the boolean table.
Step-4 : Store the count of distinguishable states in a variable(say temp).
Step-5 : Traverse each row(i) and column(j) of the table.
Step-6 : Find the transition of i and j on a given input. Say the transition states are x and y respectively.
Step-7 : If table[x][y] is false then set table[i][j] and table[j][i] as false as well.
Step-8 : Track the count of distinguishable states.
Step-9 : Repeat Steps 6-8 for all the input symbols.
Step-10 : If the variable “temp” value is not equal to the count of distinguishable states, then go to Step-4.
Step-11 : Display the distinguishable table.
Step-12 : Combine the states which are identified as equivalent by the distinguishable table and make them as a single state in minimized DFA.
Step-13 : Keep the states that are not equivalent as individual states in the minimized DFA.
Step-15 : Determine the transitions for the states of the minimized DFA.
Step-16 : Display the transition table of the minimized DFA along with its initial and final states.
4 . REGULAR EXPRESSION TO NFA WITH EPSILON MOVES
Algorithm:
Step-1 : Prompt the user for the Regular Expression.
Step-2 : Extract all the sub-expressions from the given Regular Expression.
Step-3 : Create a new state in NFA with epsilon moves whenever it is required.
Step-4 : For all the extracted sub-expressions, store their equivalent transitions in the NFA with epsilon moves.
Step-5 : Evaluate the union operation and store its equivalent transition in the NFA with epsilon moves.
Step-6 : Evaluate the closure operation and store its equivalent transition in the NFA with epsilon moves.
Step-7 : Concatenate all the sub-expressions and store the transitions for the concatenation operation.
Steo-8 : Resultant NFA with epsilon moves will have same input symbols as in the given Regular Expression along with epsilon.
Step-9 : Mark the start state as initial state and the end state as final state.
Step-10 : Display the transition table of the resultant NFA with epsilon moves along with it’s initial and final state.