Coders Packet

Converting a given Regular Expression into an NFA states table using Java

By Saptneel Sharma

This project takes a regular expression as input and converts it into an NFA, then displays the states and transitions using a table in Java

Rules for input RE:

1. It can contain the four characters a, b, c, d, and 4 operators '.', '|', '*', '+'

2. Using '.' is necessary for concatenation, i.e., expression 'ab' is incorrect, 'a.b' is correct.

 

Once RE is given:

First, we need to convert the given RE into a postfix expression.

Then, we can start scanning the string character by character. For each character, we perform a different algorithm based on the 4 basic rules of RE to NFA conversion. The states required for NFA construction are represented by the Node class. Each node contains ArrayLists for each input type given, i.e., ArrayList Node.a represents list of nodes we can jump to if input character 'a' is received at the given node. Similarly, Node.e represents epsilon/empty transitions. The node class also maintains a static variable for the count of nodes.

We do these operations while maintaining Start and Final state stacks where the top Nodes represent the start and the final state of our NFA.

Then, we create a table for states and their transitions. Starting with the Start node, we traverse the states and add their ArrayLists to the table.

Finally, we print that table.

 

Note: The final table contains a lot of unnecessary epsilon transitions. It can always be minimized later to remove some of those transitions. 

Download project

Reviews Report

Submitted by Saptneel Sharma (saptneel)

Download packets of source code on Coders Packet