AUTOMATA


	The Formal Languages Environment AUTOMATA
Introduction	AUTOMATA is a tool for modelling automata and experimenting with grammars. The environment deals with: finite state automata - FSA, both deterministic and non deterministic push-down automata - PDA, both deterministic and non deterministic finite state transducers, Moore and Mealy machines grammars regular expressions pattern matching, a module to generate automata given a pattern matching problem It provides the visualisation of some important algorithms, such as the transformation of non deterministic automata into deterministic ones or the minimisation. The automata are defined by entering their state diagram in a graphic editor or by giving a grammar. An example of a finite state automaton, accepting strings of even number of a's and b's, and its equivalent regular grammar. There is available a concise tutorial on automata theory and the AUTOMATA manual. To down-load the prototype
Contents	A finite state automaton is a mathematical model of systems which have a finite number of internal states and respond to external world just by changing their internal state. A finite state machine can be croach Automata theory is very rich and elegant. It is a mathematical subject that have several practical and useful applications but it is usually introduced very formally to students. Nevertheless scientists are often asked to design automata to describe systems. It is therefore important to be able to practice and experiment with them and not only to deal with formal theorems. Moreover it is important to become familiar with different equivalent formalisms to deal with the same problem. The application allows to interactively design an automaton, to simulate it on an input and to learn about the equivalent grammar. A PDA during back-tracking
Implementation	The application allows: to define an automaton, FSA or PDA, giving its state diagram and to simulate its computation step by step on a given input string to deal with non determinism and back-tracking to minimise a FSA to visualize the algorithm to transform a non deterministic FSA into a deterministic one to compute the regular expression of a FSA and viceversa to generate the FSA providing solution to a pattern matching problem to compute the grammar of the language accepted by an automaton to define and simulate finite state transducers, in particular the so called Moore and Mealy machines to define type-3 and type-2 grammars. The Grammar module provides several functionalities: simplification of the grammar computation of different equivalent forms derivation of productions and visualization of the derivation tree computation of the equivalent automaton, finite or push-down control of the membership of a given word to a language The Grammar module: its look-and-feel