Removal of Useless Productions

The removal of useless productions involves three steps:

1. Finding the variables that derive terminals
2. Visualizing the dependency graph
3. Modifying the grammar to remove the useless productions

Each step must be done in order. Below is a picture of the useless production removal window:

Step 1: Finding variables that derive terminals
The variables that derive terminals are the variables that have only terminals or variables that derive terminals on the right side of their productions. Input these variables into the input field separated by commas or spaces. Then, press "Check" to verify that it is correct. If you want to see the correct answer press "Show".

Step 2: Visualizing the dependency graph
When you press the "Visualize Productions" button, the visualization window is invoked. In order to visualize the dependency graph, right click on the variables to add a final state (a second circle) to the states if the state either has a production of terminal or has a production that derives terminals. In addition, transitions need to be added from each variable to every other variable that occurs on the right hand side of its productions. This allows for the visualization of which variables are actually used and which are useless. For more information, click here.

Step 3: Modifying the grammar to remove the useless productions
Modifying the grammar involves removing and adding new productions. In the left pane, the grammar that is being modified is shown. In the right pane, the initial grammar is provided for reference. Four operations can be performed when modifying a grammar:

• Adding New Rules - To add a new rule, enter the production in the input fields then press the "Add New Rule" button
• Remove Rules - To remove rules from the production, highlight the rules that are to be removed (you can select multiple rules) by clicking on them with the left mouse button. Then, press the "Remove Selected Rule(s)" button.
• Checking the Answer - press the "Check Answer" button to ensure that the modifications are correct.
• Showing the Answer - press the "Show Answer" if you just want to see the resulting grammar and move on.

Modifying the grammar to remove useless productions only involves removing productions. The variables that you can not get to from the start symbol (directly or indirectly) and those that never terminate should be removed. In other words, for any variable A there should be a 'path' to it from the start symbol, i.e. S -> aFb -> aaFb -> aaCtb -> aaABtb and for any variable A there should be a 'path' which ends in terminals, i.e. A -> aS -> aaBb -> aabb. Thus, all the variables that are not in the list of variables that derive terminals should be removed. In addition, any associated productions corresponding to the removed variables should be removed. Next, the variables which do not have a path from the start vertex in the dependency graph should be removed along with their associated productions.

Step 4: Continuing
To continue on to the next transformation press the "Next Transformation" button. If you want to parse the grammar to see the derivation of an acceptance string then press the "Parse" button.