Programming Assignment

Assignment done as a part of course Automata Theory | spring 2021

Regex to NFA

1. Convert regex expression to postfix according to predefined operator precedence(Shunting Yard).
2. Expression obtained in above step undergoes Thompson contruction to finally produce the e-NFA. Details of the thompson construction are as follows:-
   • We produce NFA's for different conditions(symbol,union,concatenation,kleene) and push them onto stack one by one.
   • When we encounter union or concatenation in our expression, we pop two NFAs out of the stack and club them together along with the operator. Now the transition functions generated by clubbing them are appended to the transition_function list.
   • When we encounter kleene operator, the correspoinding epsilon nfa and the transitions are pushed into the transition_function list.
3. When the whole expression is traversed, we store the obtained epsilon NFA as a json object.

NFA to DFA

1. We create a power set of the NFA states, those will be the states of the DFA.
2. The epsilon closure set of the start state of the NFA will be the start state of our DFA.
3. All those states in the power state which include the final state of the NFA will be considered as the final states of the DFA.
4. The transition function will be generated by taking the union of the transitions of a particular state in the power state.

DFA to regex

1. We need to take care of following cases:-
   • If there exists any incoming edge to the initial state, then create a new initial state having no incoming edge to it.
   • If there exists multiple final states in the DFA, then convert all the final states into non-final states and create a new single final state.
   • If there exists any outgoing edge from the final state, then create a new final state having no outgoing edge from it.
2. After this we eliminate the states one by one. The order of eliminating the states will start from that state which has the least number of incoming + outgoing edges.
3. Add a concatenation between the source state and the destination transitions of the destination state.
4. For states with a self transition, add a kleen star.
5. For same destination on different letters from the same source, add a union operator between them.

Minimize DFA

1. Remove all the dead and inaccessible states. This can be done by calculating number of incoming and outgoing edges for each state and removing them if some state has all but outgoing edges.
2. Using equivalence theorem, we create partitions of our set of final states and non final states.
3. We stop once when there is no further partitioning required.
4. Finally these partitions will be the states of the minimal dfa. The transition functions will be calculated according to the old dfa.