Peggy Li - JFLAP Papers

As part of my research experience, I will be reading a number of published papers about JFLAP and related topics such as algorithm and software visualization, formal languages and automata theory, and other software or tools with similar purposes. This page will chronicle the papers I have read and include a link and summary of each.

A Visual and Interactive Automata Theory Course with JFLAP 4.0

Authors: Ryan Cavalcante, Thomas Finley, Susan H. Rodger

This paper describes JFLAP 4.0, which covers more chapters of material for a finite automata course compared to the previous version, JFLAP 3.1 (now 11 out of 13 chapters for a semester-long course). JFLAP 4.0 improves upon the visualization and interactive aspect of JFLAP 3.1 and also includes many new features, including:

New approaches for converting from a Regular Expression (RE) to a Nondeterministic Finite Automaton (NFA), and vice versa
LL and LR parsing, allowing users to build parse tables and parse strings based on a given Context-Free Grammar (CFG). The parsing is modelled on JellRap, and includes functionality like detecting errors and allowing the user to handle conflicts for grammars that are not LL(1) or LR(1)
Brute force parsing that uses exhaustive search to derive a string and improves on Pâté's brute force parser
L-systems, which go beyond standard L-system tools by supporting 3-dimensional systems, commands that take arguments, and contextual commands
Transformation of a Context-Free Grammar (CFG) to Chomsky Normal Form (CNF) by removing lambda productions, unit productions, and useless productions
Multi-tape Turing machines, with up to five tapes
Comparing two finite automata for equivalence, and combining multiple automata in one window

JFLAP has been used in the CPS 140 course at Duke University for problem-solving, debugging, illustrating proofs, and relating to other computer science concepts such as run time, and both in lectures and as a homework tool. It has generally been positively received by students and was used in over 40 countries with 3800 downloads of JFLAP 4.0, as of 2004.

Turning Automata Theory into a Hands-on Course

Authors: Susan H. Rodger, Bart Bressler, Thomas Finley, Stephen Reading

This papers discusses how JFLAP aims to facilitate students' hands-on exploration of Formal Languages and Automata (FLA) topics, which a number of other existing FLA software tools also strive to do. In addition to allowing users to construct/simulate and convert between various types of automata/grammars and regular expressions and to create L-system models, JFLAP makes it easier to solve problems that are tedious to do by hand with paper and pencil, including:

Comparison of finite automata to determine if two Finite Automata (FA) accept the same language.
Comparison of regular expressions to determine their equivalency by first converting to FA.
Working backwards to recreate a NFA given its DFA form with labelled states, then comparing the equivalence of the new NFA with given DFA to check the answer
Creating automata based on properties, such as the union of two DFAs or a property applied to a regular language
Determining distinguishable states to convert to a minimal state DFA by placing distinguishable states into separate sets
Exploring nondeterminism, for example to determine if a string is a palindrome
Exponential growth in grammars and the effect on brute force parsing by transforming to an equivalent grammar (e.g. with lambda and unit productions removed)
Determining the language of a grammar by diving it into smaller components and using "temporary terminals" to determine what each variable derives
Extended study of Follow sets and showing a sentential form for each symbol in the Follow set of a grammar
Two approaches to SLR parsing: 1. converting a SLR(1) grammar to a NPDA and running different inputs, choosing lookaheads and freezing non-chosen configurations to make the parsing deterministic 2. building a SLR(1) parse table to parse the same inputs with the same lookaheads
Parsing grammars that are not SLR(1) by letting the user choose a conflict for each entry with conflicts, in order to parse the string
Running the Universal Turing Machine with input consisting of an encoded Turing machine followed by an encoded input string
Comparing 1-tape and 2-tape Turing Machines by building both for aⁿbⁿcⁿ and comparing their run times

JFLAP has a new feature called building blocks, allowing users to create and save simpler machines that can be imported as components of more complex machines. Building blocks can be connected using standard transitions, edited and renamed, and simulate input strings. It is also now possible to rename states and run transducers with multiple inputs. There have been over 25,000 downloads of JFLAP in over 120 countries since January 2003, primarily for academic uses.

Changes to JFLAP to Increase its Use in Courses

Authors: Susan H. Rodger, Henry Qin, Jonathan Su

This very short paper summarizes the changes and additions made to JFLAP as of 2011 and which were demonstrated during the referenced session. These new features include:

Undo and Redo buttons in the Editor pane
Save automaton in png, jpg, gif, or bmp or export to svg format
Zoom functionality with slider bars for various panes
Arc labels may contain regular expressions
Pushdown automata acceptance by empty stack

Experimenting with Formal Languages Using Forlan

Author: Alley Stoughton

This paper describes the Forlan formal language theory toolset developed by Stoughton, which facilitates experimentation with formal languages. Forlan, which is embedded in the functional language Standard ML, is strongly typed and interactive, and can be used with little ML knowledge. Forlan includes implementations of numerous algorithms involving Finite Automata, Context Free Grammars, and other formal language forms. The paper uses an extended example involving a difference function for a string consisting of 0s and 1s, where diff(w) = # of 1s in w - # of 0s in w to define good and bad prefixes and substrings, which then illustrate closure properties, DFA minimization, and other Forlan features with sample code. The paper concludes by comparing Forlan to other formal language theory toolsets, which the author categorizes as either graphically oriented for smaller examples (such as JFLAP) or embedded in programming languages (like Forlan), citing the latter's benefit in allowing more sophisticated experimentation.

Fifty Years of Automata Simulation: A Review

Authors: Pinaki Chakraborty, P.C. Saxena, C.P. Katti

This paper reviews numerous automata simulators developed in the last five decades to simulate several automata forms including finite automata, pushdown automata, and Turing machines. Automata simulators can be classified as either language based automata simulators or visualization centric automata simulators. In the older language based approach, the definition of an automaton is written in a symbolic language, and the program is then processed using a compiler and interpreter or only an interpreter. Language based automata simulators can be further divided into notational language based automata simulators, assembly-like language based automata simulators, procedural language based automata simulators, and descriptive language based automata simulators. The visualization centric approach uses high quality graphics and oftentimes animation to demonstrate the workings of the automaton in various modes. Visualization centric automata simulators can be categorized according to the input they receive, either structured input (e.g. transition function table) or diagrammatic input (drawing the transition diagram). The paper cites JFLAP as the "most sophisticated tool for simulating automata" today and "the best documented among the tools for simulation of automata." In addition to describing examples of each simulator subcategory, the paper concludes by listing several general trends observed in automaton simulation research.

JHAVÉ: Supporting Algorithm Visualization

Author: Thomas L. Naps

This paper discusses algorithm visualization (AV) from an educational standpoint. I opens with a description of how high-quality graphics, although valued by researchers and experts, are not necessarily effective pedagogical tools because students may get lost trying to understand a tool designed for a more advanced audience. Interactive tools have proven to be more effective than merely having high-end graphics for initially learning an algorithm, although visualizations have still proved useful as an instructional aid (e.g. to explain an algorithm during office hours). Student engagement with AV systems have been categorized in an ITiSCE report as responding, changing, constructing, and presenting.

The Java Hosted Algorithm Visualization Environment (JHAVÉ) is a support environment for AV engines that allows the engines to easily synchronize their graphical displays with standard VCR-like controls, information and pseudocode windows, input generators, stop-and-think questions, and meaningful content generation tools. JHAVÉ uses a client-server architecture; AV engines that use JHAVÉ must be written in Java and derive the abstract Visualizer class, implementing various methods and a constructor with an input stream parameter. JHAVÉ is operating system independent and allows for a variety of visualizations that do not have to be written in Java. Future work seeks to address improving student engagement and developing materials to minimize the time investment required from instructors using JHAVÉ.

A User-Centred Approach for Designing Algorithm Visualizations

Author: Sami Khuri

This paper discusses a user-centered framework for designing algorithm visualizations that are developed with real users and their specific needs and tasks in mind, since many visualizations neglect the analysis of requirements stage before proceeding to system design and implementation. Khuri identifies several aspects of the analysis of requirements:

Users analysis: categorizing users as student, educator, researcher, or developer, or as novice versus experienced users
Needs analysis: different learning styles; features for active interaction; is it appropriate to visualize the algorithm in the first place
Tasks analysis: design system based on intended goal (e.g. editor for letting novices design visualizations)
Information analysis: determine how to best visualize information depending on its content; unified view (one graphical representation for different algorithms) versus unique view (unique representation for each algorithm); direct representation (data structures directly mapped to picture) versus structural representation (some information hidden and rest is directly represented); use of color, sound, etc.
Scope analysis: scope ranges from single-purpose visualizations to specialized systems; design small first and plan a phased growth
Resource analysis: selecting a specification method (annotation, declaration, manipulation, predefinition)