JFLAP

Last updated
JFLAP
Developer(s) Susan H. Rodger, Duke University
Stable release
7.1 / 2018
Repository
Platform Java SE
Available in English
Type educational software
Website www.jflap.org   OOjs UI icon edit-ltr-progressive.svg

JFLAP (Java Formal Languages and Automata Package) is interactive educational software written in Java for experimenting with topics in the computer science area of formal languages and automata theory, primarily intended for use at the undergraduate level or as an advanced topic for high school. JFLAP allows one to create and simulate structures, such as programming a finite state machine, and experiment with proofs, such as converting a nondeterministic finite automaton (NFA) to a deterministic finite automaton (DFA).

Contents

JFLAP is developed and maintained at Duke University, with support from the National Science Foundation since 1993. It is freeware and the source code of the most recent version is available, but under some restrictions. [1] JFLAP runs as a Java application.

History

Before JFLAP, there were several software tools related to automata theory developed by Susan H. Rodger and her students starting around 1990 in the Computer Science Department at Rensselaer Polytechnic Institute. In 1992, the first published paper at a DIMACS 2012 workshop described a related tool called NPDA [2] (the paper was published later in 1994 in a DIMACS series). [3] NPDA then evolved into FLAP, including also finite state machines and Turing machines. In 1993, a paper on Formal Languages and Automata Package (FLAP) was published . [4] At that time, the tool was written in C++ and X Window. Around 1994, Rodger moved to Duke University and continued tool development. Around 1996, FLAP was converted to Java and the first paper mentioned JFLAP was published in 1996 [5] Along the way, other tools were developed as stand alone tools and then later integrated into JFLAP. For example, a paper in 1999 described how JFLAP now allowed one to experiment with construction type proofs, such as converting an NFA to a DFA to a minimal state DFA, and as another example, converting NPDA to CFG and vice versa. [6] In 2002 JFLAP was converted to Swing. In 2005-2007 a study was run with fourteen institutions using JFLAP. A paper on this study in 2009 showed that students using JFLAP thought JFLAP made them feel more engaged in the class, and made learning the concepts easier. [7]

The history of JFLAP is covered on the jflap.org site, and includes over 35 students from Rensselaer Polytechnic Institute and Duke University who have worked on JFLAP and related tools since 1990.

A paper by Chakraborty, Saxena and Katti entitled "Fifty years of automata simulation: a review" in ACM Inroads magazine in December 2011 stated the following about JFLAP: [8] "The effort put into developing this tool is unparalleled in the field of simulation of automata. As a result, today it is the most sophisticated tool for simulating automata. It now covers a large number of topics on automata and related fields. The tool is also the best documented among the tools for simulation of automata." and "The tool uses state of the art graphics and is one of the easiest to use. The tool is undoubtedly the most widely used tool for simulation of automata developed to date. Thousands of students have used it at numerous universities in more than a hundred countries."

Topics covered in JFLAP

Topics on regular language include:

Topics on context-free language include:

Topics on recursively enumerable language:

Other related topics:

Releases

JFLAP is currently released as Version 7.1.

Awards

In 2007, Rodger and her students were a Finalist in the NEEDS Premier Award for Excellence in Engineering Education Courseware for the software JFLAP. [9]

In 2014, Rodger was awarded the ACM Karl V. Karlstrom Outstanding Educator Award for her contributions to CS education, including the development of JFLAP. [10]

Books on JFLAP

Rodger and Thomas Finley wrote a book on JFLAP in 2006 [11] that can be used as a supplemental book with an automata theory course. Gopalakrishnan wrote a book on Computation Engineering [12] and in his book he encourages the use of JFLAP for experimenting with machines. JFLAP is also suggested to use for exercises. Mordechai Ben-Ari wrote a book entitled Principles of the SPIN model checker [13] and JFLAP is referenced in the book. In particular the Visualizing Nondeterminism (VN) software the book is about reads finite automata in JFLAP file format. Maxim Mozgovoy wrote an automata theory textbook in which he uses screen shots from JFLAP [14] Other people have written books that refer to the use of JFLAP in some way; several are mentioned on the JFLAP web site.

Related Research Articles

<span class="mw-page-title-main">Finite-state machine</span> Mathematical model of computation

A finite-state machine (FSM) or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types—deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one.

<span class="mw-page-title-main">Pushdown automaton</span> Type of automaton

In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.

<span class="mw-page-title-main">Automata theory</span> Study of abstract machines and automata

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states and transitions. As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.

Sheila Adele Greibach is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los Angeles, and notable work include working with Seymour Ginsburg and Michael A. Harrison in context-sensitive parsing using the stack automaton model.

In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree. Every non-empty context-free language admits an ambiguous grammar by introducing e.g. a duplicate rule. A language that only admits ambiguous grammars is called an inherently ambiguous language. Deterministic context-free grammars are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if

In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton.

In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.

In computer science, a linear bounded automaton is a restricted form of Turing machine.

In automata theory, a deterministic pushdown automaton is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.

In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, meaning that they admit an unambiguous grammar. There are non-deterministic unambiguous CFLs, so DCFLs form a proper subset of unambiguous CFLs.

In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the deterministic context-free languages. DCFGs are always unambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.

<span class="mw-page-title-main">Counter automaton</span>

In computer science, more particular in the theory of formal languages, a counter automaton, or counter machine, is a pushdown automaton with only two symbols, and the initial symbol in , the finite set of stack symbols.

In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words, so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that area.

In automata theory, a branch of theoretical computer science, an ω-automaton is a variation of finite automata that runs on infinite, rather than finite, strings as input. Since ω-automata do not stop, they have a variety of acceptance conditions rather than simply a set of accepting states.

<span class="mw-page-title-main">Weighted automaton</span> Finite-state machine where edges carry weights

In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers. Finite-state machines are only capable of answering decision problems; they take as input a string and produce a Boolean output, i.e. either "accept" or "reject". In contrast, weighted automata produce a quantitative output, for example a count of how many answers are possible on a given input string, or a probability of how likely the input string is according to a probability distribution. They are one of the simplest studied models of quantitative automata.

State complexity is an area of theoretical computer science dealing with the size of abstract automata, such as different kinds of finite automata. The classical result in the area is that simulating an -state nondeterministic finite automaton by a deterministic finite automaton requires exactly states in the worst case.

References

  1. ↑ Susan H. Rodger. "JFLAP 7.0 LICENSE" . Retrieved 2 October 2016.
  2. ↑ D. Caugherty; S. H. Rodger (1992). "NPDA: A Tool for Visualizing and Simulating Nondeterministic Pushdown Automata". DIMACS Workshop March 12–14, 1992: 365–377.
  3. ↑ Nathaniel Dean and Gregory E. Shannon, Editors (1994). DIMACS Series in Discrete Mathematics and Theoretical Computer Science: Computational Support for Discrete Mathematics, DIMACS Workshop, March 12-14, 1992. Vol. 15. United States of America: American Mathematical Society. ISBN   0821866052.{{cite book}}: |author= has generic name (help)
  4. ↑ M. LoSacco; S. H. Rodger (1993). "FLAP: A Tool for Drawing and Simulating Automata". EDMEDIA '93, World Conference on Educational Multimedia and Hypermedia: 310–317.
  5. ↑ M. Procopiuc, O. Procopiuc; S. Rodger (1996). "Visualization and Interaction in the Computer Science Formal Languages Course with JFLAP". 1996 Frontiers in Education Conference: 121–125.
  6. ↑ E. Gramond; S. H. Rodger (1999). "Using JFLAP to interact with theorems in automata theory". The proceedings of the thirtieth SIGCSE technical symposium on Computer science education. pp. 336–340. doi:10.1145/299649.299800. ISBN   1581130856. S2CID   15210587.
  7. ↑ Susan H. Rodger; Eric Wiebe; Kyung Min Lee; Chris Morgan; Kareem Omar; Jonathan Su (2009). "Increasing Engagement in Automata Theory with JFLAP". Fortieth SIGCSE Technical Symposium on Computer Science Education: 403–407.
  8. ↑ P. Chakraborty; P.C. Saxena; C. P. Katti (2011). "Fifty years of automata simulation: a review". ACM Inroads. 2 (4): 59–70. doi:10.1145/2038876.2038893. S2CID   6446749.
  9. ↑ NEEDS Premier press release: http://www.jflap.org/Premier2007_pressrelease_v2.pdf Archived 2013-02-03 at the Wayback Machine
  10. ↑ ACM announcement: http://awards.acm.org/award_winners/rodger_2853521.cfm
  11. ↑ Susan Rodger; Thomas Finley (2006). JFLAP: An Interactive Formal Languages and Automata Package. Sudbury, MA: Jones and Bartlett. ISBN   0-7637-3834-4.
  12. ↑ G. L. Gopalakrishnan (2006). Computation Engineering: Applied Automata Theory and Logic. Springer Science+Business Media LLC. ISBN   978-0387244181.
  13. ↑ Mordachai Ben-Ari (2008). Principles of the Spin Model Checker. Springer-Verlag London Limited. ISBN   978-1846287695.
  14. ↑ Maxim Mozgovoy (2010). Algorithms, Languages, Automata, and Compilers. Jones and Bartlett. ISBN   978-0763776275.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.