JFLAP8 beta

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

META-INF/MANIFEST.MF
Manifest-Version: 1.0
Class-Path: .
Main-Class: oldnewstuff.main.JFLAP
DOCS/README
Whenever the user chooses "Help" from the help menu, JFLAP searches for a
URL based on the class name of the currently active view in the
environment. (The help function has other options available as well.) 
Therefore, to add help for a view that is an instance of a class or
subclass of gui.wingdoodle.ClassBoy, merely add
"gui.wingdoodle.ClassBoy.html" to this directory.
DOCS/combineAutomata.html
Combine Automata
This combines two automata to form a new automata. When invoked in one automaton, this oeprator searches for one or more automaton of the same type. The user then has a chance to select which of the others he wishes to combine with this automaton. Once selected, a new automaton with the states and transitions of both appears. Since an automaton may have only one initial state, the initial state of the automaton chosen in the dialog box is discarded. No transitions between the two automata will be created.
DOCS/error.html
You have encountered an error within JFLAP we apparently did not anticipate. Please, copy and paste the report below in an email to rodger@cs.duke.edu. Please make sure you:
		Are running the most recent version of JFLAP,
		Copy and paste the contents of the box below as a report.
		Also include a detailed description of what you were doing.
Alternatively, you may ignore this message if you'd rather not be bothered, but we do appreciate reports.
DOCS/fastSimulator.html
Fast Run...
This operator runs input on a machine without stepping. The user enters input, and JFLAP merely runs the input until the machine accepts or rejects the input, and informs the user. If the input is accepted, the trace of configurations that led to an acceptance is displayed, and the user has the option of stopping there (the "I'm done" button), or searching for alternate accepting traces in the event of nondeterminism (the "Keep looking" button).
Because Turing class machines have the ability to run forever without any guarantee of ever halting, after a large number of configurations are generated the user is prompted with the option of aborting the run, or continuing to search.
DOCS/filemenu.html
File Menu
		New
		This will allow the user to create a new, empty structure. A list of choices will allow the user to choose what type of structure to create: some variety of automaton, grammar, or regular expression.
		Open
		When chosen, an open dialog will allow the user to select and load a file previously saved with JFLAP.
		Save
		The structure in the window for this menu item will be saved to its file. If this structure does not have a file yet, this menu item will behave like "Save As", described below.
		Save As
		A save dialog will allow the user to choose a location and name for a file; once entered, the structure for the current window will be saved to that file. Further, the structure will thence be associated with that file.
		Dismiss Tab
		In every window there is at least one tab (tabs are shown just below the menu bar). If the user is done with the currently active tab, they may select this menu item to get rid of that tab. Some tabs cannot be dismissed, in which event the menu item will be grayed out.
		Close
		The current structure's window will be closed. If the structure has not been saved recently, it shall be.
		Quit
		All windows will be closed, and JFLAP will exit.
DOCS/gui.action.LambdaHighlightAction$LambdaPane.html
Highlight Lambda Transitions
This will highlight all lambda transitions. This operator may be applied to all machine types, but since only FAs and PDAs may have lambda transitions it will only produce useful results for those types of machines.
DOCS/gui.action.MultipleSimulateAction$MultiplePane.html
Multiple Run
This operator acts similarly to the "Fast Run" operator, except that it is able to run multiple inputs on a machine and acceptance traces cannot be viewed. The inputs to run are entered in a table. The left column of the table holds the inputs.
When the "Run Inputs" button is pressed, the right column of the table reports whether that input was accepted or not. The "Clear" button will delete all inputs. The "Enter Lambda" will blank the currently selected input, acting as though nothing were truly entered in that part of the table. The "View Trace" button returns a trace of the last configuration generated for a run.
There may be an arbitrary number of inputs. Similar to grammar input, when the last row of the table is edited, a new row will be added. Additionally, the input entries will be remembered between separate multiple input runs; this is useful if a user wants to check a batch of inputs on a variety of machines without having to retype the inputs, which is useful for grading purposes (for example).
The alternate "Multiple Run (Transducer)" action is applicable only to Turing machines, and behaves similarly to the regular multiple runs, except it produces not only whether the machine accepted, but also the output from each of the tapes. In other words, it runs the Turing machine as a transducer that not only accepts a given input but modifies it. The output for a tape is defined to be the contents of the tape from the symbol under tape head, and all symbols to the right of the tape head until the next blank tape symbol.
DOCS/gui.action.NewAction.html
Welcome to JFLAP.
To start using this program,
choose a machine type.
DOCS/gui.action.NondeterminismAction$NondeterminismPane.html
Highlight Nondeterminism
This operator may be applied to all machine types. It highlights those states that are nondeterministic, i.e., those states with nondeterministic transitions.
The above diagram shows an example NFA with nondeterministic states q0 and q3. q0 is obviously nondeterministic because of the a transitions. q3 is nondeterministic because JFLAP always considers any state with lambda transitions to be nondeterministic.
DOCS/gui.deterministic.ConversionPane.html
NFA to DFA
This operator may be applied to any nondeterministic FA. At the end of the operation, there will be a completed NFA.
The conversion practice used is the standard canonical method of creating an equivalent DFA from an NFA, that is: each state in the DFA being built corresponds to a nonempty set of states in the original NFA. Therefore, for an NFA with n states, there are potentially 2n - 1 states in the DFA, though realistically this upper bound is rarely met.
The interface for the creating a DFA from an NFA is shown above. The NFA is displayed for reference purposes in the left portion of the view. The DFA is created in the right portion of the view; in the example given, the conversion is complete and correct. The set of NFA states in shown in the label below each DFA state. Between the two diagrams for the two automatons is a bar that may be dragged left and right to adjust the allocation of sizes between the two diagrams.
Expansion of States
The first thing that happens is that the initial state is created. The initial state's set for the DFA consists of the initial set of the NFA, and the closure of all states reachable from that initial state on lambda transitions. This is done for the user: the only thing the user sees at first in the DFA constructor is this one initial state. In the example above, the initial NFA state is q0 and there are no lambda transitions from it, so the initial set is only 0.
One then uses the "Expand Group on Terminal" tool () to build the DFA. When this tool is active, one drags from a state (or group) into empty space.
The user is then queried
as to what symbol to expand this group on, shown above. For example, for the initial set of q0, one can expand on 1 since there are transitions from that state in the original NFA.
Assuming that the original set of states actually expands on the input terminal, the user is then queried above the set of NFA states that group expands to on that terminal. In our running example, from the diagram we see that q0 expands on 1 to the states q0, q1 and q2. While q0 and q1 are fairly obvious, less obvious is the presence of q2. However, since there is a lambda transition from q1 to q2, the closure of q1 implies q2.
One would therefore enter 0 1 2 into the dialog shown above, as shown. (JFLAP would also accept q0 q1 q2, or 0,1,2, or q0, q1, q2, etc etc.)
When the user enters the set of states, and it is correct, the new DFA state is created at the point in empty space where the user originally dragged to. (If the user is incorrect, the user is gently chastised and nothing is added.)
Final states in the DFA are those states whose NFA state sets contain at least one final state from the NFA: in the example, notice that every state in the DFA with the NFA final state q3 in its set is a final state. JFLAP will detect if the user entered any states that were final states, and if so make the state it creates a final state.
The "Done?" button will check the DFA to see if it is complete. If it is, then this completed DFA will be exported to its own window, where it may be treated like any other FA.
Help
While it is possible for one to build the DFA entirely through use of the "Expand Group on Terminal" tool (), one also has the option of letting JFLAP do some or all of the work.
The "State Expander" tool () is a moderate help tool. When active, if you click on a state, it will expand that group on all terminals to all other groups it goes to. Any newly created states will be randomly placed.
The "Complete" button will complete the DFA entirely.
Details and Detritus
The NFA to DFA procedure depends on having transitions with at most one character. As JFLAP allows multiple character transitions, all of these are automatically broken up: the transition abc would be broken into three transitions, with two new bridge states created.
Additionally, when expanding a set of states, if the destination set of states is already in the DFA, instead of dragging to empty space, one may drag to that second set of states, and the user will not be queried as to the set of states it goes to. It is considered that the user has already made that choice. However, if the user does drag to empty space and input a set that already exists, then a new state will not be created; it clearly does not do to have multiple identical sets.
DOCS/gui.editor.EditorPane.html
The Automaton Editor
Editing a finite automaton.
The Editor Pane
The editor pane has two main components. On the top is a detachable tool bar (the section with the four iconic buttons), and on the bottom is the canvas where the automaton is drawn.
The automaton is edited through clicks on the canvas. The current action taken in response to those clicks depends on the currently selected tool. Notice in the picture that the first button, the one with the mouse cursor, is selected: this indicates that it is selected.
To select another tool, click on it, or use its shortcut key. You can get the shortcut key, as well as a short description of the tool, by holding the cursor over the tool button. After a short time this should display a tool-tip with information.
The descriptions for those tools are shown below.
The Tools
		 The State Tool (the "S" key)
		While the state tool is selected, a click on the canvas will create a new state centered at the point that was clicked.
		 The Transition Tool (the "T" key)
		By dragging from one state to another, a transition from the first state clicked to the second state dragged to will be created. Looping transitions from a state to itself are handled no differently. Once two states are joined with the tool, the user will then be asked for certain parameters of the transitions.
		 The Delete Tool (the "D" key)
		This will erase any transition or state it is clicked on. If a state is deleted, those transitions incident on or emanating from a state will be deleted as well.
		 The Attribute Tool (the "A" key)
		This tool is used to modify existing states and transitions. To move states, drag them with this tool. Dragging transitions will move transitions. Clicking on a transition edits a transition. A user may right-click (control click on Macs that have only one mouse button) on a state to bring up a pop-up menu to define the state as final, to define the state as initial, to set its label (an auxiliary description for a state), to clear its label (if it has one), or to clear all labels of all states.
Right-clicking in a blank portion of the canvas will bring up a different pop-up menu. One option of this menu is to hide or show labels; if labels are hiden, the user may hold the mouse cursor over a state to bring up a tool-tip with the label for that state. The other option is the graph layout algorithm, which will rearrange the states of the automaton. As a nota bene, this popup menu is available in all views with an automaton; however, as one might expect the user may use the graph layout algorithm only where JFLAP allows the moving of states.
Editing Transitions
Only one transition may be edited at a time. While a transition is being edited, fields appear that allow the user to change parameters regarding that particular transition. Each field corresponds to a particular parameter of that transition. In order to find out which is which during runtime, hold the mouse cursor over one of the fields; a tool tip will pop up to tell what it is.
Note that separate transitions must be placed in separate transitions; for example, in a FA, the three separate transitions a, c, and d cannot be abbreviated as the single transition a, c, d.
Editing a Turing machine transition.
A finite automaton's transition editor will have a single field representing what characters are read from the input. A pushdown automaton's transition editor will have three fields, the first to define what characters to read from input, the second to define what characters to pop from the stack, and the third to define what characters to push. A Turing machine's transition editor will also have three fields, one for the read character, one for the write character, and one for the direction to move the tape head (L, S, and R for left, stay, and right). To select the direction, click on the direction field and select from the menu or type shift-L, shift-S, or shift-R when the direction field is selected. A multi-tape Turing machine is similar, but it has as many rows as tapes; each row follows the convention of Turing machine transitions defined previously. To enter lambda entries for FAs and PDAs, simply leave a field blank. Leaving a field blank in a Turing machine is not lambda, but is the blank tape symbol (represented as a square).
To stop editing, take some other action with the tool, or click in an empty space on the canvas, or press return/enter. To cancel the editing of a transition and to revert that transition to its state before the edit, press escape. If there is anything irregular about the transition entered, the program will display an error and revert the transition to its state before the edit. Currently, the only restriction on transitions are on transitions for Turing machine: a Turing machine transition must read exactly one character and write exactly one character per tape. If the read or write fields for a Turing machine are left empty, the blank tape alphabet symbol is assumed to be the content
of that field. Pressing shift-return/enter will stop editing the transition, and begin the process of editing a new one between the start and end states of the transition that we just stopped editing.
In Haiku
In the editor,
The canvas dominates all,
The tool-bar's on top.
Choose a different tool.
Your clicks upon the canvas
now serve different ends.
Clicks on the canvas
make new automaton states
when this tool's active.
This creates transitions.
From one state to another
one may drag the mouse.
A table pops up
to define the transition.
When done, press return.
If in editing
mistakes are made in entry
escape will cancel.
State or transitions
are removed from the canvas
through use of this tool.
This changes attributes.
A click edits transitions,
dragging states moves states.
Right click on a state.
A menu lets you make it
final or initial.
To switch tools quickly
without much mousing about
use the shortcut keys.
Tools each have tool-tips.
Mouse over a tool to see it.
The shortcut's shown there.
When you are finished,
to apply an operation,
choose from the menu.
DOCS/gui.grammar.GrammarInputPane.html
The Grammar Editor
In JFLAP grammars are edited and displayed in a simple table, as shown above. Each row corresponds to a single production. The left and right columns correspond to the left and right sides of a production, naturally. To enter a rule in a particular row, select the leftmost cell of that row and type in the left hand side of the rule. Then select the rightmost column (the arrow in the middle column will appear automatically) and enter the right hand side of the rule. Lambda productions have blank right hand sides. Every symbol in the grammar is assumed to be a single character, with upper case letters as the variables, and all other characters as terminals. The left hand side of the production in the first row is always assumed to be the start variable. The table is automatically grown by one row if the last row is ever edited.
In the above picture, for example, the grammar shown has the variable set {S, A, B}, and the terminal set {a, b}. The start variable is S. There are the productions S AB, A a, B bB, and B . So, the language accepted by this grammar is ab*, that is, a followed by zero or more bs.
Unlike automaton editing, the type of grammar is not defined at the time when editing begins. Rather, many of the operators applied to grammars have conditions that a grammar must satisfy. This is to say that JFLAP will notify the user of constraints upon a grammar when the user attempts to apply an operation to the grammar.
DOCS/gui.grammar.automata.ConvertPane.html
Automaton to Grammar Converters
Incomplete conversion of an FA to a grammar
To add the productions for an object, click on an object that corresponds to a production in the FA. If a grammar production is selected, the object in the automaton that it was generated by will be highlighted. Eventually all productions will be added, and the grammar may be exported. For an FA, there will be exactly one production for every transition and final state. For a PDA, there will be productions for only transitions, though there may be many of them. Specialized notes for these two operations are written below.
The tool bar has some helpful controls:
		Hint
		This will convert one object (transition or, in the case of FA, final state) to the appropriate set of productions.
		Show All
		All remaining productions will be added.
		What's Left?
		All convertible but as yet unconverted objects will be highlighted.
		Export
		Once conversion has finished, the grammar may be output.
FA to Grammar
This operation converts a FA to a regular (specifically right linear) grammar. This operation is featured in the window above. Each state in the FA corresponds to a variable in the grammar, which is shown slung beneath each state. The terminals for the grammar are the symbols on the transitions.
Each transition and each final state correspond to a production in the grammar, with finals states correspond to lambda productions, and for a transition of a between two states labeled A to B, the production A aB is added.
PDA to Grammar
The conversion from PDA to Context-Free Grammar requires that the PDA have a certain form before the conversion begins:
		only one final state
		accepts only if stack is empty
		each transition has the form: a,A; or a,A;BC
In the PDA transformation, all variables in the resulting Context Free Grammar (CFG) will be formed from two states and a symbol from the alphabet. In other words, one variable is represented in the form qiAqj where i and j are numbers corresponding to states in the PDA and A is a symbol in the alphabet of the PDA.
The actual rule generating begins with the starting rule. The variable for the starting rule is found by concatenating the initial state with the end of stack character(Z) and the beginning state.
For example, if an automata had an initial state q0 and a final state q3, the starting rule would be Sq0Zq3.
Once the starting state is established, the transitions must be processed. 
		Transitions of the form a, A; from state qi to state qj are converted to qiAqja
		Transitions of the form a, A; BC from state qi to state qj are converted to the set of rules:
{ qiAqx a (qjBqy) (qyCqx) | qx and qy are states in the automaton}.
 
When exporting, each of the qiAqj symbols has a single character variable substituted in its place.
DOCS/gui.grammar.convert.ConvertPane.html
Grammar to Automaton Converters
Completed LL Conversion of a Grammar
Completed LR Conversion of a Grammar
There are three options to transform a grammar to an automaton: "Convert to PDA (LL)", "Convert to PDA (LR)", and "Convert Right Linear Grammar to FA". Any restricted grammar may be transformed to a PDA by either the LL or LR algorithm, while converting a grammar to an FA requires a right-linear grammar. Every production in a right-linear grammar has on the right hand side at most one variable, which is to the right of any terminals.
The grammar to PDA interfaces (both LL and LR) are shown above. In the LL converter, each production on the left side of the window corresponds to a loop transition on the middle state of the automaton. By selecting productions in the left hand side, if the corresponding transition has already been created it is highlighted. A small checkbox next to each productions reveals if it has been created yet.
In these sorts of converters, each production in the grammar corresponds to a transition. There is an automaton editor in which a user enters transitions normally. If the transition the user enters does not correspond to any production, she is notified and the transition is removed. Other controls are available as well:
		Show All
		
		All required transitions are added.
		Create Selected
		
		This will take all selected productions in the left table and add the corresponding transition.
		Done?
		
		This will check if anything remains to be done. If something remains, the user is informed. If nothing remains, the user is informed to this effect and is then allowed to export the resulting PDA.
		Export
		
		Once all the transitions that need to be added are added, and the user has checked whether she is done yet, the user may export and use this newly built automaton with this control.
DOCS/gui.grammar.parse.BruteParsePane.html
Brute Parser
Parsing an unrestricted grammar.
JFLAP can not only parse grammars with parse tables,
but can attempt a brute force substitution parse as well. This sort of parse works not only for restricted grammars, but unrestricted grammars as well where there may be terminals and multiple symbols on the left hand side. A simple unrestricted grammar is shown above.
First, one enters a string to attempt to parse in the text field labeled "Input." When one has entered the string, one either presses "Start" or types return to begin the process of parsing. The brute force parser will attempt to parse the string. The first accepting parse found will be shown.
This method of parsing can take a very long time since it explores every possibility of substitution of variables. Moreover, since the language accepted by unrestricted grammars is equivalent to Turing recognizable languages, there is no guarantee that the brute force parser will ever stop in the event of an unrestricted brute force parse. An example is the grammar shown in the example picture above: attempt to parse ab on that grammar and it will never terminate. If a parse is taking too long for the user's taste, pressing "Pause" will halt it. The search can be resumed by pressing "Resume." If another string is input while the searcher is searching, the original search will be terminated in favor of the new search.
During the course of this search, a small display will indicate how many non-pruned nodes have been added to the tree. Another (faster changing) value in parentheses will indicate how many nodes were examined in the current subtree. JFLAP performs some very aggressive pruning to make this most inefficient of routines run as quickly as possible, so there will usually be few nodes added to the tree versus the number of nodes examined.
If a string is rejected, unlike in LR(1) and LL(1) parsing there is no intermediate tree displayed; a simple message will appear below the input field. If a string is accepted, one repeatedly presses "Step" to show the next phase of the transformation. The "Input Remaining" shows what input the parser has yet to process, including a terminating $ character. The "Stack" shows the current contents of the stack. A message at the bottom of the window will show what is currently happening; in the image above, it shows that we are in the process of replacing S with aSb. JFLAP will highlight the node of the tree that was last processed on the stack. Whenever an entry in the parse table is used, that entry is highlighted in the table. One presses this step button until the accepting derivation is shown.
The default view is a non-inverted tree. In the tree, yellow nodes are the leaf nodes, i.e., terminals that are not substituted in the future. Green nodes are internal nodes, i.e., non-terminals and terminals that are substituted. An unrestricted grammar parse has the ability to combine multiple symbols together and substitute them with other symbols; this multiple parentage is achieved by grouping nodes together in a blue rounded rectangle and treating that as a single node. The other view option available is the "Derivation Table": this will show the attempts of the parser to derive the input string from the start variable, and the productions used in the process of derivation.
DOCS/gui.grammar.parse.LLParsePane.html
LL(1) Parsing
In the middle of a sample LL(1) parsing.
Before LL(1) parsing can take place, first an LL(1) parse table must be defined according to the operations defined here.
First, one enters a string to attempt to parse in the text field labeled "Input." When one has entered the string, one either presses "Start" or types return to begin the process of parsing.
After a string is entered, one repeatedly presses "Step" to show the next phase of the parse. The "Input Remaining" shows what input the parser has yet to process, including a terminating $ character. The "Stack" shows the current contents of the stack. A message at the bottom of the window will show what is currently happening; in the image above, it shows that we are in the process of replacing S with aSb. JFLAP will highlight the node of the tree that was last processed on the stack. Whenever an entry in the parse table is used, that entry is highlighted in the table. One presses this step button until the string is either accepted or rejected by the parse table.
The default view is a non-inverted tree. In the tree, yellow nodes are the leaf nodes, i.e., terminals. Green nodes are internal nodes, i.e., non-terminals. There are other view options available. The current display shows a non-inverted parse tree. Also available is an "Inverted Tree" which is the same thing drawn upside down, which is more useful for LR(1) parsing. Also available is the string derivation view: for LL(1), this will show the attempts of the parser to derive the input string from the start variable, and the productions used in this derivation.
DOCS/gui.grammar.parse.LLParseTableDerivationPane.html
Build LL(1) Parse Table
LL(1) parse table building.
The user may build a LL(1) parse table for a grammar with this operator. A full discussion of the method of building an LL(1) parse table is far too elaborate for this documentation. Rather, this assumes that one has some understanding of building LL(1) parse tables, and merely explains JFLAPs interface convention for helping the user complete this procedure.
The LL(1) parse table construction and parse tree construction algorithm is as described in the ``Dragon'' compiler book. Put very loosely, the idea behind LL(1) parsing is that the grammar starts with the start symbol, and repeatedly attempts to replace variables with their right hand side expansion based on what the next symbol of the input is, until the input string is derived.
Steps
When the user first chooses the menu item to build the parse table, JFLAP first checks to make sure that the grammar is LL(1). If it is not, then the user is warned and is given the option to abort. Assuming the grammar is LL(1), or if the user wishes to continue in spite of the grammar not being LL(1), these following steps are completed in order:
		The user first enters the first sets for each variable, i.e., the set of terminals that a variable can start with. ! serves as the special symbol for lambda. This set is entered by the user as a simple string of symbols, without any delimiters: e.g., if the user wishes to indicate that a, b, and are in the first set, then the user enters ab! as a single non-spaced string. When the user is finished defining the first sets, he or she may press "Next," and JFLAP will either move to defining the follow sets, or will notify the user about errors.
		The user then enters the follow sets for each variable, i.e., the set of terminals that can immediately follow a variable in a derivation. The input convention is the same as for the first sets, except that the $ symbol indicates the end-of-string character. When the user has finished, again "Next" may be pressed to move on or be notified of errors.
		With the first and follow sets as a reference, it is possible to fill out the entries in the parse table. Given a production A and every symbol b in FIRST(), the (b, A) entry in the table gets . Multiple entries in a table cell (possible only if the grammar is not LL(1)) are separated by spaces. The ! string represents a lambda production.
Help
Users may elect to let JFLAP do some or all of the work rather than entering data themselves.
		Do Selected
		In any of the above steps, the user enters input into cells in a table. If the user selects any of these cells and elects to "Do Selected", the answer appropriate to the cells will be entered into those cells which are currently selected. Non-selected cells shall be left alone.
		Do Step
		This will either complete all first sets, or all follow sets, or complete
the parse table according to which step we are on.
		Do All
		This will do everything. After pressing this, JFLAP should display a working parse table.
Parsing Details
The top figure shows a completed LL(1) parse table. Once the table is completed, the user has the option to proceed to parsing strings using the table by pressing the "Parse" button. The interface for that parsing is explained here. If the original grammar was not LL(1) the user will not be able to use the parse table to parse strings.
DOCS/gui.grammar.parse.LRParsePane.html
LR(1) Parsing
In the middle of a sample LR(1) parsing.
Before LR(1) parsing can take place, first an LR(1) parse table must be defined according to the operations defined here.
The interaction relevant to the parsing of strings in LR(1) parsing is identical to the parsing of strings in LL(1) parsing. See the notes on LL(1) parsing to learn about the interface.
The LR(1) parsing algorithm is, of course, very different from LL(1): the stack is used differently, and the parse is bottom-up rather than top-down as in LL(1) parsing. In addition, when reducing according to a production, the production is highlighted. However, the interface is identical.
DOCS/gui.grammar.parse.LRParseTableDerivationPane.html
Build LR(1) Parse Table
LR(1) parse table building.
The user may build a LR(1) parse table for a grammar with this operator. As with LL(1) table building, a full discussion of the method of building an LR(1) parse table is beyond the scope of this discussion. The procedure followed is more or less the same as the SLR parse table building in the Dragon compiler book.
This shares some similarities with the LL(1) parse table builder view. The similarities include the building of the first and follow sets, the operations of controls at the top of the help window and so forth. That may be helpful as a reference.
NB: In this view, you may resize the views to see things better. For example, dragging the bar between the sets of items diagram and the parse table will adjust the sizes of both.
Steps
The following steps are completed in order to build an LR(1) parse table:
		The user first enters the first and follow sets for each variable. The interaction that takes place here is identical to that of the LL(1) parse table's first and follow sets construction.
		
A set of items construction.
The next step is the construction of the sets of items in a transitional diagram. What a transitional diagram is and how it is put together is not covered here, as a full description would be prohibitively long. JFLAP represents a transitional diagram by a FA as shown in the figure at the top of the page, with each state corresponding to a set of items. The initial set of items corresponds to the initial state, and final states represent terminating sets of items. The items in a set are shown in the label below a state.
An item is essentially a production with some placeholder character; JFLAP uses an underscore, _, as this special character. A production A BCD can produce the four items A _BCD, A B_CD, A BC_D, and A BCD_. The marker _ in an item represents which symbols have been processed (to the left of the marker) and which have not been processed (to the right of the marker).
During the first part of the sets of items construction, the initial set of items is put together (i.e., S' S and its closure). To expand that set, use the transition tool (), and drag from a set to an empty space in the diagram. The user is queried as to the symbol to expand the set of items on. Once the user enters a grammar symbol and JFLAP confirms that the set of items does goto on that set, a dialog then pops up allowing the user to define the set of items.
The view used for defining a set of items is shown above. The left hand column lists those productions in the grammar. The right hand column lists items already part of the set. To add an item to the set, click a production in the left hand list. A pop-up menu will appear with all possible placements of the sets of items. To save time, the "Closure" item will take whatever items are selected in the right column, and add all items which comprise the closure of the selected item. The "Finish" button will add all items that should be in the set of items. When "OK" is pressed, the answer will be checked for mistakes. If everything is fine, a new set of items will appear at the point in the empty space that the user initially dragged to.
If the user wishes to define a transition from an existing set of items to another existing set of items, in creating the transition she may drag to the second set rather than to empty space. This will avoid the bother of defining the second set of items, as JFLAP will assume the set dragged to is that second set.
One uses the attribute tool () to drag states around, and set final and initial states as per the usual practice when editing. The attribute tool here does not have the ability to change transitions or set labels.
		Once all sets of items are constructed, the parse table is built. In the parse table, a blank entry indicates an error in parsing, s means shift, r means reduce, a single number means goto that item, and acc is accept. To change the content of a cell, click the cell and start typing. For reduction, the number following the r is a production number. The productions are indexed from 0 onward in the order shown in the list on the left. For example, in the grammar given above r1 means "reduce by S aSb." To determine the number of a production without counting, hold the mouse over the production, and a tool tip will appear with the production number. Also, you may hold the mouse over entries over a parse table to get via tool tips descriptions more comprehensible than simple r1 or s2 or what have you. When the table is completed the user may press "Next." If there are no errors, one may proceed to parse strings with that table.
Help
The style of help that is available for LR(1) table construction is nearly identical to that available for LL(1) table construction: "Do Selected," "Do Step," and "Do All" are all there and work in the same fashion.
In the case of the sets of items construction, the help options available are "Do Step" and "Do All," which will randomly place any set of items. After the items are placed, one may rearrange them to make the view more aesthetically pleasing, but it will otherwise be immutable.
Parsing Details
The top figure shows a completed LR(1) parse table. Once the table is completed, the user has the option to proceed to parsing strings using the table by pressing the "Parse" button. The interface for that parsing is explained here.
There may be at least one cell in the table with more than one rule, and the user may choose which of the rules to use before parsing. Cells with more than one expansion are highlighted in a sort of sherbet orange color. One may click on these cells, and a pop-up menu will appear allowing the user to select which expansion to use for this cell. Note that if clarifying ambiguity becomes necessary, the parse table may not accept the same language as the original grammar since, obviously, the parser will not be aware that alternate shifts/reductions/whatever exist.
DOCS/gui.grammar.transform.ChomskyPane.html
Chomsky Converter
This action is the final of four steps in transforming a grammar to Chomsky normal form (CNF). The goal is to reform the grammar so that it generates the same language as the original, but is in Chomsky normal form. A grammar in Chomsky normal form (CNF) has all productions be either to two variables, or a single terminal.
The converter works as follows: the user starts with the original
grammar, and repeatedly converts productions that are not CNF already. It works rather simply on two cases.
The first case is if a production has multiple symbols in its right hand side with at least one of those symbols as a terminal. In this case, any terminal symbols are converted to variables like so: for any terminal , a production B() will be introduced, and the variable B() will replace in the original production.
The second case is if a production has more than two variables in its right hand side, but no terminals. For example, take ABCDE. In this case, that production is replaced with the two productions ABD(n) and D(n)CDE, where n is some positive integer. One would then have to convert the D(n)CDE production.
This process is repeated until there are no productions that are not in CNF form.
As a note, the CNF converter will attempt to introduce as few new productions as it can, and will attempt to reuse existing variables and productions wherever possible.
Help & Controls
"Convert Selected" will take any production currently selected in the grammar editing view, and break it down via the method listed above; double clicking on a production accomplishes the same effect. "Do All" will make the grammar CNF in one fell swoop. "What's Left?" will highlight those productions that remain to be converted. "Export" is available only when the grammar is CNF, and will take this reformed grammar and put it in its own window.
DOCS/gui.grammar.transform.LambdaPane.html
Lambda Removal
This action is the first 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, but has no lambda productions. The goal is to have no rule in the grammar derives the empty string. The requirement is that the start variable cannot derive lambda. This operator consists of two major steps:
		The selection of variables that derive lambda.
		The modification of the grammar.
The left side of the interface shows the original grammar. The functionality of the two toolbars shall be covered later. There are three labels between the two toolbars; the first tells which step the user is currently on, the second indicates how much work remains, and the third indicates which variables derive lambda.
Selection of Lambda Variables
The first step is to select those variables that derive lambda. In the example grammar given in the picture above, obviously B and C derive lambda, but so does A because of the rule ABC.
The user indicates a variable by clicking in the grammar table to the left (which holds the original grammar); the left hand side of the production clicked is assumed to be the desired variable. For example, if the user clicks the production ABCD, then JFLAP believes the user is indicating the variable A.
In order to complete this step, the user must indicate all variables that derive lambda. As the variables are selected (and verified to be correct), they will appear in the third label that shows which variables derive lambda. The second label will indicate errors to the user if any are made.
Reforming the Grammar
The next step is to reform the grammar. There are two major parts to this: removing lambda productions, and adding new productions to ensure that the grammar accepts the same language.
To edit the grammar, use the grammar view in the lower right. Editing is like it is in the regular grammar view, with the exception that if any production is added that is not part of the reformed view, the user will be notified and it will be added. Additionally, existing productions cannot be edited: only the last row may be edited. To remove lambda productions, select those productions you wish to remove, and click the "Delete" button.
As far as what rules to add, if ABCDB is in the grammar and B and C derive lambda, the user would add the seven productions that consist of almost all permutations of the absence and presence of the variables that derive lambda, i.e., the first B, C and the second B. These are shown in the table below. (There are seven and not eight because the permutation where they are all there is already part of the grammar. Note that the variables are not really being deleted so much as they are being substituted with the empty string.)
		AD		ADB		ACD		ACDB
		ABD		ABDB		ABCD		
		Productions added for ABCDB.
	
Adding these permutations of rules can become tedious. If there is a rule which implies the addition of a large number of permutations, the user may select the rule in the left hand-side table, and press the "Complete Selected" control. This will make the additions implied by that production for the user.
There are a few caveats. First, no rule is added twice. If we had the production ABB with B deriving lambda, then the user would add the rule AB only once. Moreover, if AB just happened to be part of the grammar anyway, we would not add it at all. Additionally, in case it is not obvious, the user does not add lambda rules, so she would not add A.
Help & Controls
The "Do Step" button will complete the current step only (either detecting lambda variables, or reforming the grammar). "Do All" will complete both steps. The "Delete" and "Complete Selected" are covered in the section about reforming the grammar. "Proceed" and "Export" are available only when the grammar is completed: "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 phase of the CNF conversion, unit production removal.
DOCS/gui.grammar.transform.UnitPane.html
Unit Removal
This action is the second 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 has no unit productions. A unit production is a production with a single variable on the right hand side. This operator consists of two major steps:
		Drawing the variable dependency graph.
		Modifying the grammar to remove unit productions.
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 and the second indicates how much work remains.
Variable Dependency Graph
The first step is to draw a variable dependency graph (VDG). 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 directed graph is defined this way: there is a node for every variable, 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 unit production AB in the grammar.
The goal is to relate how variables are "connected" via unit productions, so that when we remove all unit productions we are able to better tell which relationships we need to preserve. This is discussed more later.
Reforming the Grammar
The next step is to reform the grammar. There are two major parts to this: removing unit productions, and adding new productions to ensure that the grammar accepts the same language.
Note that the interface for grammar editing is exactly the same as the reformation of the grammar with regard to the lambda production removal: we're merely adding and removing different types of productions. Since the interface is identical, it makes no sense to repeat that information.
As far as what rules to add, the idea is that if
we have the unit production AB, then to generate the same language after removing that unit production we must add A for every B production. (As a special case, note that we do not add unit productions in this substitution, so that if AB and BC are in the grammar, we do not add AC.) However, in addition to this, if there are BC and CD unit productions, we also add A and A for every C and D.
This is where the VDG comes in handy: if A is an ancestor of B in the VDG (even a non-immediate ancestor!), then for every B we add A.
Note that if we select the unit production AB in the left grammar view, and press "Complete Selected", this will add all A productions for every B production currently in the grammar that is not already part of the grammar.
Note that in the example given in the figure above, we have the rules Ba and Bb, and since both A and S are ancestors of B, both variables now have rules where they directly derive a and b.
Help & Controls
The "Do Step" button will complete the current step only (either defining the edges in the VDG, or reforming the grammar). "Do All" will complete both steps. "Do Selected" is available only when the grammar is being edited; when pressed, any selected unit productions in the grammar editing table will be deleted, and replaced with the appropriate productions. "Proceed" and "Export" are available only when the grammar is completed: "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 phase of the CNF conversion, useless production removal.
DOCS/gui.grammar.transform.UselessPane.html
Useless Removal
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.
		Determining which variables derive terminals.
		Drawing the variable dependency graph.
		Modifying the grammar to remove these useless productions.
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.
Terminal Deriving Variables
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.
Variable Dependency Graph
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.
Reforming the Grammar
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.
Help & Controls
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.
DOCS/gui.lsystem.DisplayPane.html
L-System Renderer
The L-system renderer available in the input menu allows one to take an L-system and render that system for various levels of substitution. In the example picture we see the rendering of the dragon L-system given here.
JFLAPs L-system renderer subscribes to the canonical "turtle" metaphor, that is, an imaginary entity that moves about in a world, turning this way and that, and marking its territory as it moves forward. Functionally it is similar to other L-system renderers that exist, but it has a few major differences from the majority I encountered:
		It can render 3D L-systems (albeit as orthogonal projections).
		Assignable values and parameters may take the form of mathematical expressions.
		It has an actual GUI slightly more complex than a handful of buttons and a drawing area. I don't know why this is unusual, but it is.
Definition of an L-System
Parameters
During the definition of the L-system the user has the chance to define some parameters in the table of the L-system input pane to affect the initial state of the drawing environment. What follows are a list of all recognized parameters, their default value for the renderer if they are not defined, and how they are used.
		Parameter		Default		Description
		distance		15		Lines are drawn with length distance.
		color		black		Lines are drawn with the color specified by color. Colors may be specified by name. The acceptable color names are
black,
blue,
brown,
cyan,
darkGray,
darkOliveGreen,
darkOliveGreen2,
dukeBlue,
forestGreen,
goldenrod,
gray,
green,
lightGray,
magenta,
maroon,
oliveDrab,
orange,
orangeRed,
pink,
purple,
red,
springGreen,
violetRed,
white, and
yellow. Color names are case sensitive!Additionally, one may specify a given color according to three numbers of the form a,b,c. If a, b, and c are all within the range of [0.0, 1.0], they are interpreted as hue, saturation, and brightness values respectively (where the hue range of 0 through 1 represents a full tour around the color wheel), and are used to define a color appropriately. If any of those values is outside of that range they are treated as standard red, green, blue respectively, with each channel value ranging in increasing intensity from 0 to 255 as is normal. For example, blue may be defined either as an HSB color by .667,1,1 or as an RGB color by 0,0,255.
		polygonColor		red		Polygons are filled with the color specified by polygonColor. This parameter accepts the same value types as the color parameter.
		angle		15		Whenever the turtle is turned, pitched, or rolled, it does with angle degrees. Note that this parameter may also be named by angleIncrement (a compatibility measure with my first implementation).
		hueChange		10		When the command to increment the hue of the current drawing color is given the degrees the hue is turned is hueChange.
lineWidth		1.0		Lines are drawn with a pixel-width of lineWidth. This parameter accepts real number values greater or equal to zero (e.g., 4, 1.5, 0).
		lineIncrement		1.0		When the line width (the parameter lineWidth) is incremented or decremented, it is incremented or decremented by this amount.
Drawing & Turtle Symbols
The following symbols are used to move the turtle about, and otherwise affect the state of the drawing. Whenever appropriate, a parameter will appear to indicate that the action associated with the symbol uses a quantity that can be changed. For example, & causes the turtle to pitch down by angle degrees. If the user has specified that angle=30, then the turtle will pitch down by 30 degrees.
		Symbol		Description
		g		Move forward distance in the y direction with the pen down, producing a line of width lineWidth and of color color, unless we are building a polygon, in which case a line is not drawn and the end point of this move is added to the polygon.
		g(value)		Like the above, but with a specified distance.
		f		Move forward distance in the y direction with the pen up, producing no line but changing the position of the turtle.
		f(value)		Like the above, but with a specified distance.
		+		Turn right (clockwise in 2D) by angle degrees. Turns about the z-axis.
		+(value)		Like the above, but with a specified number of degrees.
		-		Turn left (counter-clockwise in 2D) by angle degrees. Turns about the z-axis.
		-(value)		Like the above, but with a specified number of degrees.
		&		Pitch down by angle degrees. Turns about the x-axis.
		&(value)		Like the above, but with a specified number of degrees.
		^		Pitch up by angle degrees. Turns about the x-axis.
		^(value)		Like the above, but with a specified number of degrees.
		/		Roll right by angle degrees. Turns about the y-axis.
		/(value)		Like the above, but with a specified number of degrees.
		*		Roll left by angle degrees. Turns about the y-axis.
		*(value)		Like the above, but with a specified number of degrees.
		[		Begin branch (i.e. push turtle state on stack).
		]		End branch (i.e. pop turtle state from stack). If there is no corresponding [, this has no effect. Aside from restoring position and direction, any changes to variables since the last [ will be undone.
		!		Increment lineWidth by lineIncrement.
		!(value)		Like the above, but increments by the specified amount.
		~		Decrement lineWidth by lineIncrement, with a minimum lineWidth of zero attainable.
		~(value)		Like the above, but decrements by the specified amount.
		{		Begin the definition of a polygon. The turtle position when the { is processed will be the first point in the polygon, and the end point reached by each g directive until the close of the polygon will be added to the polygon.
		}		Ends the definition of a polygon. The turtle position when the } is processed will not be added to the polygon. The polygon will be filled with the color polygonColor and will have no outline.
		%		Turn by 180 degrees about the z-axis, the same axis as the + and - turns.
		#		Increments the hue angle of color by hueChange. Changing the hue angle will have no effect if color has no saturation, i.e., if color is black, grey, or white.
		#(value)		Like the above, but with a specified number of degrees.
		@		Decrements the hue angle of color by hueChange.
		@(value)		Like the above, but with a specified number of degrees.
		##		Increments the hue angle of polygonColor by hueChange. Changing the hue angle will have no effect if polygonColor has no saturation, i.e., if polygonColor is black, grey, or white.
		##(value)		Like the above, but with a specified number of degrees.
		@@		Decrements the hue angle of polygonColor by hueChange.
		@@(value)		Like the above, but with a specified number of degrees.
		parameter=value		This will attempt to set a parameter named parameter to value. For example, the symbol angle=20 will cause all subsequent turns to be made with 20 degrees, color=red will cause all subsequent g directives to produce red lines, and soforth. The names of parameters and acceptable values is the same as for the mappings in the parameter table. There must be no whitespace in the parameter=value symbol, or else it shall not be processed as a single symbol.
Values
You may have noticed that in the list of symbols were a number of symbols that take an argument, for example, the turn right symbol + can appear in the form +(value) to turn a specified number of degrees, and you can also say lineIncrement=value to set the amount the line width changes when the renderer encounters the symbols like ! and ~.
Every value may be as simple as a number, but it may be a mathematical expression involving parameters as values. One could say distance=distance+2, which will increment subsequent line lengths by 2. Moreover, if in the parameters list one specified that foo was 100, then the symbol g(3+(8+foo)/2) would yield a line of length 57. All g symbols are functionally equivalent to g(distance).
The operators allowed in a value are + (addition), - (subtraction), * (multiplication), / (division), ^ (power), ( and ) (parentheses), and they obey the usual rules of order of operations and soforth. If an undefined symbol appears in a mathematical expression, then a value of 0 is assumed for that symbol.
For higher performance, avoid the frequent use of expressions. For example, if you're curious about the relative performance of +(5*angle) versus + + + + +, the + + + + + will tend to be faster, though your milage may vary for your particular JVM.
Interface
The L-system renderer interface has 5 distinct components of interest.
		While the system is busy rendering an L-system, the progress back will report the amount done to the user.
		This field will display the current symbols being drawn up to a point; since most interesting L-systems are exponential in their growth, this will usually be omitted since longer strings of symbols are usually quite nonsensicle to the user.
		This spinner allows the user to specify the depth of L-system substitution recursion. A level of 0 means that only the axiom will be rendered.
		The major portion of the view is used to display the rendering of the L-system. If the rendering extends beyond the extent of the view, scrollbars will appear to allow the user to inspect all of the rendering.
		Though of little use for 2D rendering, for L-systems that take advantage of 3D renderings the ability to look at the rendering from different angles is important. By twiddling these values the user can get a feel for the shape of the rendering.
Notes
The 3D "renderer," as it is, is nothing more than the standard Java 2D graphics where the z coordinate is ignored for drawing. Consequences of this are that all projections are orthogonal and that lines drawn over each other may not be in sensible depth order. Until either gl4java or (heaven forbid) Java3D becomes standard issue for the JVM on all reasonable platforms, this system shall persist.
DOCS/gui.lsystem.LSystemInputPane.html
The L-System Editor
As always, this documention assumes some general familiarity with L-systems and only describes JFLAP's implementation of these structures. JFLAP allows a user to define an L-system and to render that system with an arbitrary level of substitution in three dimensions. The formal definition of an L-system requires three components, to which we add one to aid in drawing:
		System alphabet
		JFLAP does not require the user to explicityly set the alphabet (i.e. set of recognized symbols) of the system. If a symbol is does not have significance to whatever is attempting to interpret it is ignored, e.g. a renderer of an L-system would be interested in those symbols that affect the
rendering and those symbols which have replacement rules.
While the rules of replacement, the presence of an axiom, and soforth are universal to L-systems, the interpretation of those symbols to render a graphic is not part of the mathematical definition. At present there is one L-system renderer in JFLAP, and its description, including the symbols it recognizes, may be found here.
		Axiom
		At the top of the editing view is a text field for typing in the axiom labeled, appropriately enough, "axiom." As mentioned before symbols are space delimited. In the example given above, the three symbols in the axiom are +, g, and L, in that order.
		Rewriting Rules
		Below the axiom is a series of productions that represent the replacement rules; one enters these just as one would enter productions for a grammar. As with the axiom, symbols must be space delimited. In most cases you will want only one symbol on the left. The two rewriting rules in the example picture are L L + R g + and R - g L - R, that is, going from one level of substitution to the subsequent level of substitution, every L shall be replaced with the five symbols L + R g +, and every R shall be replaced with the five symbols - g L - R.
You can also have multiple symbols on the left side of the rewriting rule. JFLAP offers rules that are sensitive to context. These rules take the form of i a0 a1 ... ai-1 ai ai+1 ... an-2 an-1. In this list of n+1 symbols, the i symbol is an integer from 0 inclusive to n exclusive; the symbol ai is the symbol potentially being rewritten, but only if the string of symbols a0 a1 ... ai-1 come before it and ai+1 ... an-2 an-1 come after it. For example, the rewriting rule 2 a b c d x y z, in an expansion c would be rewritten with x y z if preceeded by the two symbols a b and the symbol d.
If multiple replacement rules dictate that a symbol is to be rewritten, one of the rules will be chosen uniformly at random when the expansion of symbols occurs. Additionally, lambda productions are allowed and indicate simply that the symbol should be removed.
		Drawing Parameters
		Below the grammar input, and at the bottom of the window, there is a table the user may set parameters that affect the rendering of the L-system. The user enters the parameter name in the left column, and its value in the right column. In the example L-system input figure, we have the two parameters named angleIncrement and distance, with values 90 and 4 respectively. Mind you, these parameter names are case sensitive! If the same parameter is defined multiple times in the table, only the last definition of the parameter is respected.
Above the right scroll bar, just to the right of the "Parameter" column label, there is a small button. If you press it, you will see a popup menu with a list of those parameters the L-system renderer in JFLAP recognizes (one can't remember them all, can we?). For a full description of these parameters, view the pages for the L-system Renderer When you select a parameter name from this list, it will be entered into the table, and you will begin editing the value for that parameter. If you select a parameter that already exists in the table, then you will begin editing the parameter value for the existing entry.
In Haiku
The axiom field
holds the starting point
of the L-system.
The middle table
displays the rewriting rules.
You edit them here!
Rewriting rules look
like a grammar production
with left and right sides.
A rule's left side holds
the symbol to replace in
derivation strings.
The right side contains
what symbols the left symbol
will be replaced with.
The strings of symbols
in JFLAP's L-systems are
space delimited.
Strings without whitespace
should therefore be considered
a single symbol.
That is important!
Don't mistake "gfgg"
for "g f g g"!
The bottom table
holds drawing parameters
for the L-system.
Parameters set
in this table change how the
L-system renders.
The left column "Name"
holds the parameter name.
Right holds the value.
As an example,
set "color" to the value "green"
and "g" draws green lines!
Also, consider
setting "distance" to "18".
Lines are that length now.
You click in the box
above the table's scroll bar
for a list of names.
Choose one of these names,
and that named parameter
shows in the table.
Want to render this?
You choose the menu item
named "Render System"
DOCS/gui.minimize.MinimizePane.html
Minimize DFA
This operation converts a DFA to another DFA that is minimized (i.e., has the least number of states possible while still accepting the same language). The process involves building a tree of groups of states that ``split'' on terminals. Once there are no sets of states that cannot be split any further, states in the same set are deemed equivalent. The user then proceeds to build a minimized DFA using these groups.
Splitting Groups
Splitting Groups
In the view, there is a toolbar along the top. To the left there is the original DFA, with the addition of the trap state (if necessary). To the right there is the tree where the set of distinguishable groups is determined.
When the tool starts out, there are two major groups: non-final and final states. The current groups are those groups in the leaf nodes. The union of all current groups is the set of all states, and all current groups are state disjoint.
A group is split on a terminal if the states in the group have transitions on this terminal to different groups. If all the transitions are to the same group, then there is no split on this group based on this terminal. If a group splits, it may split two or more ways. A group may split two or more ways.
Take the example given in the screen shot above. We start with the groups {0,1,3,4} and {2}. Notice that group {0,1,3,4} splits on a because while states {0,4} go to states in {0,1,3,4}, states {1,3} go to states in the group {2}. So, this group splits on a into the two groups {0,4} and {1,3}. Then, we note that group {0,4} splits on the terminal a again, since q0 goes to q3 which is in group {1,3}, while q4 goes to itself, which is in the current group {0,4}. So, {0,4} splits on a into the two groups {0} and {4}. (We also had the option of splitting {0,4} on b.)
Hopefully the interface is as straightforward as the theory. The tool bar along the top of the interface applies actions to the currently selected group. A group is selected if it is darkened. To select a group, click its node in the tree.
		Set Terminal
		This begins the process of splitting a group on a terminal. In order to split a node on a terminal, the terminal to split must first be entered. Once the user selects a group she may press this button, and enter a terminal to split the group on. (If the terminal does not split the group, the user is informed.)
After this is done, the process for splitting a group is started. Since splitting a group implies that at least two new groups will be created, two empty nodes appear as children to this group's node. To add a state to a group, select one of these children, and click a state in the left display. (The states in the currently selected group appear as selected states in the left DFA display. To remove a state from a group, similarly, you click the state again.)
		Auto Partition
		This will automatically split a group on some terminal. If the terminal has not yet been set on this node, a terminal that splits this group is randomly chosen. If the terminal to split this node's group on has already been chosen through "Set Terminal", then that terminal is used.
		Complete Subtree
		This will split the current group, and all children groups of this
group, and their groups, and their groups too, until in the subtree rooted at the currently selected has no groups that can be distinguished further.
		Check Node
		If one manually splits a group, to end the process of splitting a group, select the group you had split, and press "Check Node". This will check the expansion, and report mistakes. If there are no mistakes, the work shall be approved.
		Add Child
		While the "Set Terminal" operation will automatically add two children to a node, it is possible that a group splits into more than two groups. To add another subgroup to the group you're splitting, press this button while the group you're splitting is selected.
		Remove
		If the user discovers that a child added is unnecessary, she may select and remove it with this button.
		Finish
		If all the groups on the leaves cannot be distinguished further, this stops the process of building distinguishable groups, and moves to the operation of defining the final minimized DFA.
Building the Minimized DFA
Minimized DFA Building
Once the "Finish" operation confirms that the tree is fully built, the final DFA is built. The view will be replaced with an editor view, where the user builds the DFA. In the minimized DFA, each indistinguishable group of states from the original DFA is shown in the label. The group of states that include the trap state are not considered part of the minimized DFA: they are by definition unnecessary. Creating transitions is just as it is during regular FA building, with the exception that if the user adds a transition that is not part of the minimized DFA, she is notified and the transition is not added. The "Hint" button will add some transition that needs to be added. "Complete" will add all transitions that need to be added. "Done?" will check the minimized DFA to see if it is complete. If it is complete, it will be exported to another window.
DOCS/gui.regular.ConvertPane.html
Convert FA to RE
The idea behind the transformation is that an FA is repeatedly collapsed until there is a single initial and different single final state, with transitions between them. This reformed FA is called a generalized transition graph.
Steps
On screen directions walk the user through every step of the transformation.
 In the process of each step, we will pretend to convert this automaton.
		The FA is transformed so that there is a single final state that is not the initial state. First, the user creates a new final state. Then, the user inserts lambda transitions from the old final states to the new final state. This is accomplished with the regular state creator () and transition creator () tools. The transition creator knows that if we are on this step, we will only be interested in creating lambda transitions. If there is already only a single final state, this step is skipped. The example does not require this step.
		 If there are multiple transitions from and to any two given states, they are combined into a single transition. For example, if from state qi to qj there are two transitions a and b, they are combined into the regular expression transition a+b. The user does this with the "Transition Collapser" tool (). To collapse multiple transitions between states, click one of these transitions while the tool is active. If there is no pair of states with multiple transitions between them, this step is skipped.
		 Empty transitions are added between all pairs of states for which there is no transition; that is, if from qi to qj there is no transition, an empty transition is added from qi to qj. Note that empty transitions are not lambda transitions! To add empty transitions for this step, use the transition tool () as you normally do. Since this step assumes you will only be adding empty transitions, dragging out a transition will automatically create an empty transition. The example picture shows all the necessary empty transitions needed: note the empty set symbol. If there is no pair of states without a transition between them, this step is skipped.
		 At this point, all non-initial, non-final states are collapsed, one at a time. To collapse a state, select the "State Collapser" tool () tool, and click on the state you wish to collapse. In the example, the only state to collapse is q1
. When you click on a state with the collapser, a window pops up, as shown above, showing the new transitions for the automaton; as JFLAP will soon remove q1, certain transitions have to be reformed to ensure that the automaton accepts the same language. In the example window shown, from state q0 to q2, there will be a transition ((a+b)c*)(b+c). If in this window an expression is selected, in the editor, those transitions that were combined to form the expression will be highlighted. When this inspection has finished, press "Finalize" and all transitions will be 
		Once only the final and initial states remain, this generalized transition graph will yield a regular expression. One can use the "Export" button to put this expression into a regular expression environment.
As a final point, the "Do It" button will complete the current step.
DOCS/gui.regular.ConvertToAutomatonPane.html
Regular Expression to Automaton
When the converter starts up, all that appears initially are two states (one initial and one final) with a transition. The transition between them contains the regular expression that we are trying to convert.
The critical idea of the converter is that at each stage of the conversion one has a valid machine where some transitions may happen to be regular expressions. Each regular expression may be recursively broken into smaller parts. The conversion is finished when the only transitions have only single (or zero) alphabet symbols on them.
There are four types of reductions that can be done on a regular expression:
		 Transitions are first broken according to the or symbol (+). For example, the expression a+bc+d can be broken into three subexpressions a, bc and d. An example of such a breakup is shown above.
		 Transitions that cannot be broken across ors are then broken across concatenations. For example, a(b+d)c* would be broken into the three subexpressions a, (b+d), c* as shown above.
		 If the transition does not break across either concatenation or or, then it may be a Kleene star (*) term, of the form a* or (b+cd)* (shown above) or something in that vein. In this case, the user effects the removal of the Klein star.
		Lastly, if a regular expression is of the form (...), then the parentheses are simply removed from the transition.
The user interacts with the system in this way:
		In the first stage of the breakup, one uses the "de-expressionify" tool () to select a transition with a regular expression that can be broken down. If a particular transition cannot be broken down further, the user is gently chastised.
		If this is a reduction that requires additional lambda transitions, the user may add them with the transition tool (). A small message in the upper portion of the window will report how many transitions remain to add. If the user makes an error in the process of adding the transitions, the user will immediately receive a message to that effect. When all required transitions are added, the reduction is considered complete.
		Steps 1 and 2 are repeated until there are no more transitions that can be "de-expressionified."
At any time, the user may press "Do Step" to complete the current RE reduction; if no RE reduction is in progress, this will choose a transition that remains to be reduced, and reduce it. "Do All" will complete the building of the automaton.
When the automaton is fully built, as with similar conversion operations the user has the option