Sistema de Animação
de Teoremas de Equivalência entre Modelos
e Linguagens Computacionais
System of Graphic Animation of Equivalence Theorems between Computational
Models and Languages
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:
you can create your computational models and
grammars. Once they have been created they can be transformed
according to the equivalence theorems between computational models,
grammars and languages. As novel property SAGEMoLiC allows for
visualizations of equivalence relations between machine models
and language representation of regular languages.
File consists of the option
an interesting collection of Built-in Examples
and, very important,
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,
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
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
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
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).
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.
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
- 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
Link to SAGEMoLiC main page
Link to SAGEMoLiC site at the Universidade de Brasília