Skip to end of metadata
Go to start of metadata

A jar of our project can be downloaded here.

Introduction

This week I teamed up with Nick Cameron to create a project combining topics from CS231 and CS378 (Theory of Computation).  

A typical course on theoretical computation builds understanding from very simple computers to computers as powerful as the ones widely used today, covering deterministic finite automata (DFA), nondeterministic finite automata (NFA), pushdown automata (PDA), and Turing machines. All of these computational models work by taking a string as input, and returning a binary answer - accept or reject. Brief descriptions of these machines are given below. There is a free, open source learning tool to simulate these machines called JFLAP, which allows for easy creation of these machines as well as testing strings to see if they are accepted or rejected (and many other features besides). Our goal was to create a program with similar functionality using JavaFX.

Definitions:

DFA

A DFA is a type of computer that consists of a set of states, a set of characters called the alphabet, a transition function, a specified state called the start state, and specified states called accept states. They work as follows: given a string, the DFA begins at the start state, and reads the first character from the input. It attempts to follow an arrow labeled with the character it has read to another state - possibly the same one (the arrows are the transition function). If it cannot follow an arrow, it rejects the input. For each additional character in the input, the DFA tries to follow an arrow labeled with the character. If the string is not rejected by the end of the input, then we check if the final state we have reached is an accept state. In such cases, the string is accepted. If the DFA finishes in any other state, the string is rejected. The set of strings that a finite automata accepts are called its language. There are some restrictions to DFAs, including but not limited to: there must only be a finite number of states, each state must have at most one transition (arrow) for each character in the alphabet, and there can be no "empty transitions". An empty transition is explained below.

NFA

A NFA has the same structure and rules as a DFA, but there are less restrictions, and as a result, a differently defined transition function. Transitions may be "empty" which means that an arrow can be followed without "using up" a character from the input. These transitions are labeled with the lowercase greek epsilon - e. There is also no limit to the number of transitions per character in the alphabet, e.g. one state may transition to itself for the character 1 and to another state. This is the case in the right example above. A NFA, when given a character from its string input, may then be in one state or another (or many others). This means that multiple paths through the NFA may be followed for the same string. To determine whether a string is accepted, the NFA effectively follows all paths, and if any finish in an accept state, the string is accepted. If none of the paths lead to an accept state, the string is rejected.

The Project

To create our application, we first developed classes to simulate finite automata without any visual displays or user input. These classes were designed to serve as a model for the rest of our program and provide the backbone for all of its functionality. We broke up the tasks of the automata in the natural way by creating classes to represent states, transitions, and the automatas themselves. We also created a class called RegularOperations for the model which included static methods to preform the regular operations of union, intersection, concatenation, complement, and Kleene star on finite automata.  These operations create a new finite automata which recognizes the given operation applied to the languages of each finite automata in the operation.

To display the model to the user, we created a JavaFX display using code and fxml files creating using scene builder.  To allow user input, we created a set of classes designed to serve as an interface between the model and the view.  

Here are the key features we've included up to this point:

  • Visual construction of finite automata
  • String testing  by steps (forwards and backwards) which allows the machine's state to be tracked as it transitions
  • Batch string testing for an automata
  • Undo and Redo buttons for all automata changes
  • Automata loading and saving using Java serialization, complete with indicators and warnings for trying to close unsaved content
  • Menu options for applying regular operations to finite automata, for example giving the union of the languages accepted by two already present finite automata
  • Aesthetic transitions with arrowheads and arcs
  • Testing for equivalence, emptiness, and determinism

Here are some pictures of our program:







Design

Throughout the project, we tried to adhere to Model-View-Controller design architecture. As discussed, our model consists of an independent finite automata class, and the ability to perform regular operations on such finite automata.

This design style can be extremely helpful for large projects because large and interlinking classes can be difficult to debug and make updating and expanding almost impossible. Adhering to the style can be difficult, though, as its strictness can make solving some problems more difficult. For example, in our project, keeping the three areas separate required some creative solutions so we would not to pollute the model with details which truly belong to the visuals or controller. While it would have made things much easier initially to store position data in the model, it is a detail only used for display purposes. Our solution was to create mappings of states to positions whenever necessary. Though it was frustrating to manage and seemed to be overly complicated, one noticeable benefit was that implementing undo and redo functionality was considerably easier after having followed the MVC design.

Pitfalls

Learning to use JavaFX was very difficult at first, but as with using MVC, this was definitely rewarding toward the end. JavaFX has many features that make it much easier to work with than Swing, given a bit of experience.  I wish I had started with JavaFX at the beginning of the semester so that I could have gotten over the initial learning curve and had more time to use it to its full potential.

Transitions were very difficult to work with. They are currently displayed as an arc between 3 points, but that caused a pretty serious bug when any of the points occupied the same position, and a less serious bug when the points were colinear. Our solution was to "bump" the point being moved very slightly if it would cause either of those problems. Adding arrowheads that pointed to the target nodes required a lot of careful thought - finding the intersection and angles between two circles can be a lengthy process.  In general, we struggled with the fact that JavaFX (and Swing) use increasing y-coordinates going down instead of up as expected.  When handling complex geometric problems, it is confusing to have to adjust your intuition.

Shortcomings

  • A huge problem and waste of time was JavaFX's TableView implementation. When editing a table, users expect to be able to click somewhere else and have their changes saved. Many tables behave like this automatically, but JavaFX requires some pretty ugly hacks to get the same functionality. Trying to fix this problem took quite a long time, and in the end we were not successful.
  • There are a couple more things we would like to include in the model, for example: DFA minimization, NFA to DFA conversions, pushdown automata, turning machines, and other computational models.
  • There are always more features to add like exporting automata as an image and different algorithms for visually organizing states.
Labels