B
in the grammar, i.e., B appears in the right hand side of some production of A. The goal is to relate how variables depend on each other.This action is the third of four steps in transforming a grammar to Chomsky normal form. The goal is to reform the grammar so that it generates the same language as the original, but any useless productions are removed.
The left side of the interface shows the original grammar. The functionality of the two toolbars (top and middle) shall be covered later. There are two labels between the top toolbar and the variable dependency graph; the first tells which step the user is currently on, the second indicates how much work remains.
The first step is to determine which variables are even capable of deriving terminals. One can have those variables that derive only terminals, and then repeatedly find variables that have productions with only those variables and terminals, and repeat this process until no terminals are added.
The interface for the user to input these variables is identical to the interface for the user to input which variables derive lambda in the lambda production remover, so you are referred there for information about that interface.
The second step is to draw a variable dependency graph (VDG) among those variables that derive terminals. As you can see, drawing a variable dependency graph uses the same interface for defining an automaton. The regular arrow tool is there for moving variable nodes about, and the transition tool is there to define edges. The initial variable in the grammar is represented as an initial state in an automaton.
The directed graph is defined this way: there is a node for every variable that derives a terminal, with the variable name displayed inside the node. The user has the responsibility of defining the edges in the VDG. An edge exists from node A to B in the VDG if and only if there is a production AB in the grammar, i.e., B appears in the right hand side of some production of A. The goal is to relate how variables depend on each other.
The last step is to reform the grammar. (Those rules with variables that do not derive terminals are automatically removed and will not appear.) In this case, one need only remove those productions that are useless.
At this stage, a useless production is a production with some variable V, where V in the VDG does not have the start variable's node as an ancestor. The deletion of those productions is handled just as it is when deleting lambda productions in the lambda production remover's grammar interface, so look there for help with the interface.
The "Do Step" button will complete the current step only (either detecting terminal deriving variables, or defining the VDG, or deleting useless productions). "Do All" will complete both steps. "Proceed" and "Export" are available only when all useless productions have been removed: "Export" will take this reformed grammar and put it in its own window, while "Proceed" will take the reformed grammar and go to the next and last phase of the CNF conversion, Chomsky normal form converter.