# Getting Started with Cora¶

(version 22/06/2021)

## A short, but necessary, presentation of Awali. ¶

Awali is written in C++ and is organised into three layers: the static, the dynamic, and the interface layers.

The core of the platform is the static level, which provides the data structures and a library of algorithms. The type of a weighted automaton -- called the context -- is determined by the type of weights and the type of labels. Every algorithm is implemented via template functions working on template classes, and is compiled for the type of automata that are used. Efficiency is partly based upon this generic programming which is anyway essential when dealing with weighted automata.

The dynamic level allows both the call of functions of the static level and genuine C++ programming with the use of a kind of universal type of automata. This type is an abstraction of template (static) types of automata; it gives access to a complete template-free API for weighted automata. A remarkable feature of the dynamic level is the on-request compilation of modules (data structures and algorithms) from the static level. Even written at the dynamic level, programs are compiled and not interpreted at execution time.

The interface level offers for the time being two kinds of access to the lower layers: a command-line interface, called Cora, which allows the call to most of the algorithms of the static level, and a Python interface to both the dynamic and the static levels.

The easiest way to begin with Awali platform is probably to play with the command-line module Cora.

## What is at hand ¶

After Awali installation, the command

In [1]:
!cora help

cora is the line command interface to the Awali platform for
computing automata and transducers.

Usage:  cora [options] <command> <argument> [<argument2>]

where, in most cases, <command> is a function applied to <argument>, usually
an automaton, a transducer, or a rational (regular) expression ('ratexp' in
awali parlance). The [options] bring more information to <command>, from the
type of some parameters in <argument> to the input or output format to the
method to be used for the computation.

There are more than 80 commands. To give an overview
cora list commands
prints (almost) all commands, organised in a table showing 6 'kinds':
'basic-cmds', 'generic-cmds', 'wfa-cmds', 'nfa-cmds', 'ratexp-cmds', and
'transducer-cmds', and
cora list <kind>
prints the list of the commands in the category <kind> together with a short
description for each command. More classically,
cora help <cmd>
prints a more detailed description of the command <cmd>, whereas
cora help <option>
gives more information on the option <option>.

By default, the result of <command> is output on the 'standard output'. This is
sensible when the result is a number, a word, or a (small) ratexp. Not when
the result is an automaton or a (long) ratexp, in which case the output is to
be redirected to a file, and the command line looks then like:

cora <command> <argument>  >  <result-file>

Commands can be 'piped' in order to compose the commands:

cora <command1> <argument> \| <command2> - \| <command3> -  >  <result-file>

In this case, the '-' refer to the result of the previous command. Such
composition of functions avoids the transformation, forth and back, between
the inner representation of automata (or ratexps) and their linearisation
in files.

A number of automata and ratexps are stored to serve as examples in command
lines. Accordingly, a number of 'factories' allow to build automata that depend
on one, or two, parameters. Automata and expressions can take their 'weights'
or 'coefficients' in various semirings or 'weightsets'.
cora list automata (or ratexps or factories or weightsets)
gives the list of such available examples or weightsets.

Finally, some elements of the Awali platform have been documented in such a way
that the corresponding information can be called from cora with the command
cora doc <page> in addition to being readable in the Doxygen pages.



yields the list of available commands (89, without counting the options we'll explain below).

$cora help <command>  donne un peu plus d'informations sur la commande <command>, eg: In [2]: !cora help determinize   Usage : cora determinize <aut> Compute the determinization of the Boolean automoaton <aut>. The result may not be complete.  The command In [3]: !cora list automata  Automata library : ================== Name: Description: ---------------- -------------------------------------------------------------- a1 ............. NFA that accepts words with at least one factor 'ab' ab ............. NFA with epsilon transition which recognizes words in 'a*b*' b1 ............. Z-FA that counts the number of 'b' in words of {a,b}* binary ......... Z-FA that converts words of {0,1}^* into their binary values binary-int ..... Z-FA that converts words of {0,1}^* into their binary values c1 ............. Z-FA that converts words of {a,b}^* into their binary values d1 ............. Z-FA computes the difference between the numbers of 'a' and 'b' e1 ............. Q-FA that converts words of {a,b}^* into their binary values after the radix point evena .......... DFA which recognizes words with an even number of 'a' fibotdc-lr ..... Sequential transducer which tries to replace 'abb' by 'baa' flipper ........ Transducer that mimics a flipper game gray ........... Gray code increment heapmodel ...... Z-max-plus automaton, heap model with 2 pieces lamplighter .... Group automaton which realizes the Lamplighter group minab .......... Z-min-plus-automaton which computes the minimum among the numbers of 'a' and 'b' in every word minblocka ...... Z-min-plus-automaton which computes the length of the shortest block of 'a' in every word oddb ........... DFA which recognizes words with an odd number of 'b' prob-rabin ..... R-automaton (probabilistic automaton) that accepts w with prob. expansion(w) rotation ....... C-automaton realizing a rotation slowcerny ...... Synchronisable NFA which meets Cerny bound slowgrow ....... Z-min-plus-automaton with a slow growing length function url-validator .. Automaton with epsilon transition that validates url  yields the list of preloaded automata that are part of Awali distribution (11 presently). ## The first command¶ A quite natural way to get used with Cora commands is to apply them on preloaded automata and, to begin with, with preloaded Boolean automata. For instance the command: In [4]: !cora info a1   Automaton : a1 Weightset : B Label type : Letters Letter type : Character Alphabet : { a, b } 3 states 6 transitions 1 initial state 1 final state  yields informations (number of states, of transitions, etc.) on the automaton a1. The two lines displayed before this output explain what is going on during the waiting time. Awali is installed without that any function at the static level be compiled. When the first function is called or, later, when a function that has not been compiled yet is called, Awali recognises it, launches the compilation of a group of functions (a module) for the "type" of the automaton that is used by the command (the context), create the corresponding links, and executes the command. If the same command is repeated, the answer is immediate (unless the computation time is noticeable) as Awali will have recognised that the necessary function is already compiled. In what follows, we will not show these messages anymore. The "context" will be explained below (or not). In [5]: !cora display a1  opens a pdf viewer which display a graphical representation of a1 generated by Graphviz. ## Some classical functions¶ In [6]: !cora determinize a1 > a1det.json  computes the determinisation of a1 and stores it, under json format, in the file a1det.json. This automaton that is just created (and which is stored in the current directory) can be called as an operand by any other command. In [7]: !cora -Na1det display a1det.json  displays a1det in another window. Thanks to option -N, the name of the temporary file is a1det; without it would have been tmp and the old window would have been updated. In [8]: !cora min-quotient a1det.json \| display -  computes the minimal quotient of a1det and displays it in the window tmp. This line shows how it is possible to chain commands in Cora by means of a kind of "fake pipe" : the result of the first command is sent to the seconde one which receive it by means of the -. For instance, Brzozowski's method for the computaion of the minimal automaton of the language accepted by an automaton may be written (on one line): In [9]: !cora transpose a1 \| determinize - \| transpose - \| determinize - \| display -  Awali of course implements Kleene Theorem and produce a rational (regular) expression from an automaton: In [10]: !cora aut-to-exp a1  (a+b)*(ab)(a+b)*  The method used to compute the expression is the state elimination method (is there really another one?) together with an elementary, natural, and efficient heuristic. ## Construction of automata¶ A first method to constructing an automaton is to use the converse part of Kleene Theorem: In [11]: !cora exp-to-aut '(a+b)*(ab)(a+b)*' \| display -  The method used to building this automaton is the one of derived terms, that is the automaton obtained is the one often called Antimirov automaton. Using options, one can also build, with the standard method, the standard automaton of the expression, also called Glushkov or position automaton, which has obviously 7 states: In [12]: !cora -Mstandard exp-to-aut '(a+b)*(ab)(a+b)*' \| display -  or the Thompson automaton with the thompson method: In [13]: !cora -Mthompson exp-to-aut '(a+b)*(ab)(a+b)*' \| display -  The alphabet on which the automaton is built is implicitely the set of letters that occur in the rational expression that is considered. It could be conceived that the alphabet is indeed strictly larger, as in the following example where the option -A allows to specify the alphabet explicitely: In [14]: !cora -Aabc exp-to-aut '(a+b)*(ab)(a+b)*' \| display -  The result is not different from the one obtained before. The difference appears when one tries to make the automaton complete: In [15]: !cora -Aabc exp-to-aut '(a+b)*(ab)(a+b)*' \| complete - \| display -  Another method for building automata with Cora consists in using the edit command in order to add, or suppress, states, or transitions, to an automaton that already exists: $ cora edit a1



or the create command to build an automaton from scratch -- with the specification of the alphabet if the default one A={a,b} is not sufficient:

$cora -Aabcd create  These two commands open an interactive session in the terminal. ## Other commands¶ Cora offers a large number of commands, the name of which are self-explanatory in general. In particular, it accepts all commands present in Grail or in Fado. Notice the difference between $ cora minimal-automaton <aut>



which computes the minimal automaton of the language accepted by the (Boolean) automaton <aut> and

\$ cora min-quotient <aut>



which computes le minimal quotient of <aut> (also called minimal bisimulation).

## Input--Output¶

The automata created with Cora (or Awali), and those which are preloaded, are stored under json format (hence the extension in the above examples). Remark that no extension is used for calling preloaded automata, it is the way they are distinguished from others.

One can write an automaton under that json format with the cat command:

In [16]:
!cora cat a1

{"format": {"name":"fsm-json", "version":"1"},
"kind":"Automaton",
{"name":"a1",
"caption":"NFA that accepts words with at least one factor 'ab'",
"creator": {"programName":"awali", "version":"2.0.0-rc2"},
"timestamp": {"date":"2021-06-22", "time":"06:35:52Z"}},
"context":
{"labels":
{"labelKind":"Letters", "letterType":"Char", "alphabet":["a","b"]},
"weights": {"semiring":"B"}},
"data":
{"states":
[{"id":0, "name":"p", "initial":true},
{"id":1, "name":"q"},
{"id":2, "name":"r", "final":true}],
"transitions":
[{"source":0, "destination":0, "label":"a"},
{"source":0, "destination":0, "label":"b"},
{"source":2, "destination":2, "label":"a"},
{"source":2, "destination":2, "label":"b"},
{"source":0, "destination":1, "label":"a"},
{"source":1, "destination":2, "label":"b"}]}}


Cora, and Awali, output, and read automata written under other description formats, namely those used by the Grail and Fado platforms (for Boolean automata only):

In [17]:
!cora -Ograil cat a1

(START) |- p
p a p
p a q
p b p
q b r
r a r
r b r
r -| (FINAL)


Rational expressions can be read, and output, under a text or a jsonformat. Under the text format, they are written between quotes (for input). In order to be input from a file, they should necessarily be stored under the json format.

In [18]:
!cora cat 'a+b'

a+b

In [19]:
!cora -Ojson cat 'a+b' > e.json
!cora -Ijson cat  e.json

a+b


Further features of Cora, in particular the computations with weighted automata and with transducers, will be treated in other notebooks and pieces of documentation.