SAGEMoLiC

Authors: A.H.R. da Silva and A.F. da Fonseca, R.B. Nogueira and M. Ayala-Rincón

SAGEMoLiC is easy to use Guided by the menues:

• File
• Language
• Edit
• Alphabet
• Operations
• Simulation
• Visualization

File consists of the option Exit , an interesting collection of Built-in Examples and, very important, Open and Save options which allow for locally saving all new examples the user creates using remotely SAGEMoLiC. In this way, the user can recover his/her examples in subsequent sections.

Language here you can select the type of language. Currently either regular language or context-free language. The default is regular language. Notice that according to your selection of class of languages, the corresponding built-in examples are active and the other ones inactive.

Edit consists of options for finite automata and push-down automata design according to the kind of selected language (Regular Language and Context Free Language, respectively).  Once a kind of language has been selected (and this selection is essential for building automata as well as for loading built-in examples), you can create and delete states and transitions between them.    Additionally, Edit includes a selection Arrow that allows for replacement os states as well as of transitions.
After selection of Create Transition the transitions between states are constructed selecting with the left button of the mouse the source and destiny states and an intermediate point, where it will be indicated the direction and eventually the alphabet symbol (and the stack symbol) of the transition.
After creating the states, clicking twice with the mouse you can define a sole start state and a set of final states.

 Alphabet allows for definition of the alphabet (and the stack) symbols.  Once they have been selected, you can include information about these symbols in the transitions of the created automata clicking twice on the transitions with the mouse.

Edit and Alphabet may be used alternatively for creating automata (but symbols labelling transitions can only be used after being included in the alphabet).

Operations

• for the case of regular languages allows for translations of non deterministic finite state automata with empty transitions into equivalent reduced deterministic finite state automata step by step.  Also a corresponding regular grammar can be generated. Moreover, in this menu it is possible to give a regular expression, for which a corresponding automata is created, that by step by step translations may be transformed into an equivalent reduced finite state automata.
• for the case of the context-free languages allows for simulation of grammar derivation, direct grammar translations to the Greibach and Chomsky normal forms and direct translation of grammars in pushdown automata.

Simulation allows for insertion of words in the language of the alphabet symbols of the current automaton and then for a nice visualization of its execution in the current machine. This simulation is flexible and dynamic: you can speed up and slow down the simulation during execution; pause, continue, stop, etc. during execution.

Visualization allows for graphic illustration of the key principles that make machine models and language representations of regular language equivalent. Only the nontrivial equivalence relations are implemented:

• Regular languages
  • Lambda-NDFAs vs NFAs: here the user can visualize how a sequence of transitions from a state to another, that consists of pure lambda-transitions except for a transition labeled with an alphabet symbol, say a, can be associated (and replaced) with a sole transition labeled with a, from the beginning to the end state of the sequence. The key notion involved in this equivalence, that is the lambda closure, is explained and illustrated. Additionally, this visualization helps to understand why the existence of a sequence of pure lambda-transitions from a non-final state to a final state allows us to change the beginning state of the sequence from non-final to final. The former corresponds to the reachability ("for free") of final states from a non-final state or equivalently to the existence of final states in the lambda closure of a non-final state.
  • DNFAs vs DFAs: here the user can visualize how non-determinism in FAs corresponds to the possibility of reaching a subset of states of the initial set of states. Beginning from the initial state and examining symbol by symbol of the alphabet, new composed states are generated in a second canvas where the corresponiding DFA is bein generated.
  • DFAs vs reduced DFAs: here the user can visualize the notions of distinguishable and indistinguishable states, that justify the existence of minimal automata.
  • (Lambda-N)DFAs vs REs: here the user can observe in detail how the original transitions of a given finite automaton can be extended to equivalent transitions, whose labels are regular expressions. And how this basic conversion principle allows for construction of a regular expression equivalent to the finite automaton.
• Context-free languages
  • CFG normalization to Greibach or Chomsky normal form: here the user can observe step by step the conversion of context-free grammars to their Chomsky or Greibach normal forms.
  • CFG translation to pushdown automata: this option allows for a nice visualization of the construction of a pushdown automaton from a context-free grammar that previously should be translated into the Greibach normal form.

• Graphical representation of transition diagrams for automata that are generated after applying some translation is unclear, because the system randomly chooses unused positions in the current canvas to place the new states and transitions. A general geometrical solution for this problem is very hard, since it is related with the efficient bi-dimensional representation of graph. To make clear the current transition diagram, the user may, during the whole visualization or translation process, rearrange states and transitions by simple use of the mouse. This works whenever the Array option of the Edit menu is activated.
• Size of the canvas changes from a browser to another. In particular, the selection buttons Automatic Mode and Interactive Mode from the different visualization control canvas are hidden under some browsers. In order to make visible these buttons the user may enlarge the corresponding canvas by standard application of the mouse.
• We have detected some difficulties when trying to activate some buttons of SAGEMoLiC in Linux platforms such as Red-Hat and Slackware. We are working on making the system as portable as possible.