The Vaucanson TAF-Kit 1.0 User's Manual - LRDE
Contents
1. product auti aut2 Give the product of auti by aut2 quotient aut Give the quotient of aut realtime aut Give the realtime version of aut standardize aut Give the standard automaton of aut union of standard auti aut2 Give the union of standard automata concat of standard auti aut2 Give the concatenation of standard automata star of standard aut Give the star of automaton aut sum auti aut2 Give the sum of auti and aut2 transpose aut Transpose the automaton aut trim aut Trim the automaton aut Conversion between automata and expressions aut to exp aut Give the automaton associated to aut derived term exp Use derivative to compute the automaton of exp to aut exp Alias of standard exp expand exp Expand exp standard exp Give the standard automaton of exp thompson exp Give the Thompson automaton of exp 18 Chapter 3 Automaton Library VAUCANSON comes with a set of interesting automata that can be used to toy with TAF KIT Chapter 2 for instance In the chapter we present each one of these automata 3 1 Boolean Automata 3 1 1 al A 3 states 6 transitions 1 1 T 1 19 3 1 2 bl A 2 states 5 transitions I 1 T 1 3 1 3 div3base2 A 3 states 6 transitions I 1 T 1 3 1 4 double 3 1 A 3 states 6 transitions 1 1 T 1 202. and vcsn z min plus run as program algorithm name arguments vcsn z list commands List of available commands Input output work define automaton file Define an automaton from scratch display aut Display aut dot dump aut Dump dot output of aut dump automaton file Dump a predefined automaton edit automaton file Edit an existing automaton identity aut Return aut info aut Print useful infos about aut list automata List predefined automata Tests and evaluation on automata are isomorphic auti aut2 Return whether auti and aut2 are isomorphic eval aut word Evaluate word on aut is ambiguous aut Return whether aut is ambiguous is complete aut Return whether aut is complete is empty aut Return whether trimed aut is empty is realtime aut Return whether aut is realtime is standard aut Return whether aut is standard Generic algorithms for automata accessible aut Give the maximal accessible subautomaton of aut eps removal aut Give aut closed over epsilon transitions eps removal sp aut Give aut closed over epsilon transitions co accessible aut Give the maximal coaccessible subautomaton of aut complete aut Give the complete version of aut 17 concatenate auti aut2 Concatenate aut1 and aut2 power aut n Give the power of aut by n
3. The transducer T only accepts binary numbers divisible by 3 vcsn tdc dump automaton t1 vcsn tdc alphabeti ab domain gt div by 3 xml Now the file divisible by 3 xml contains the description of a Boolean automaton that accepts only the numbers divisible by 3 vcsn b dot dump div by 3 xml gt div by 3 dot 14 A 3 states 4 transitions I 1 T 2 2 2 2 Available functions The following functions are available for both vesn rw tdc and vcsn tdc programs To invoke them run program algorithm name arguments vcsn tdc list commands List of available commands Input output work define automaton file Define an automaton from scratch display aut Display aut dot dump aut Dump dot output of aut dump automaton file Dump a predefined automaton edit automaton file Edit an existing automaton identity aut Return aut info aut Print useful infos about aut list automata List predefined automata Tests and evaluation on transducers are isomorphic auti aut2 Test if auti and aut2 are isomorphic is empty aut Test if aut realizes the empty relation is sub normalized aut Test if aut is sub normalized Generic algorithm for transducers eps removal aut epsilon removal algorithm eps removal sp aut epsilon removal algorithm domain aut Give the automaton that accepts all inputs accepted by aut eval aut
4. trim aut Trim the automaton aut Boolean automaton specific algorithms complement aut Complement aut determinize aut Give the determinized automaton of aut minimize aut Give the minimized of aut Hopcroft algorithm minimize moore aut Give the minimized of aut Moore algorithm Conversion between automata and expressions aut to exp aut Give the automaton associated to aut derived term exp Use derivative to compute the automaton of exp to aut exp Alias of standard expand exp Expand exp standard exp Give the standard automaton of thompson exp Give the Thompson automaton of exp exp exp 13 010 iji The transducer computing the quotient by 3 of a binary number Figure 2 2 Rational weight transducer 7 2 2 Transducers While the VAUCANSON library supports two views of transducers currently TAF KIT only pro vides one view vcsn tdc considering a transducer as a weighted automaton of a product of free monoid In a forthcoming release TAF KIT will provide vcsn rw tdc considering a transducer as a machine that takes a word as input and produce another word as two tape automata Both views are equivalent and VAUCANSON provides algorithms to pass from a view to the other one 2 2 1 Example To experiment with transducers we will use 71 described in Figure 2 2 and part of the automaton library Section 3 3 1 Domain
5. automaton vcsn b dump automaton al lt automaton name al xmlns http vaucanson lrde epita fr gt lt labelType gt lt monoid generatorType letters type free gt b b The graphical layout of this automaton was described by hand using the Vaucanson G ETEX package However the following figures are generated by TAF KIT giving a very nice layout yet slightly less artistic Figure 2 1 The automaton A lt generator value a gt lt generator value b gt lt monoid gt lt semiring operations classical set B gt lt labelType gt lt content gt lt states gt lt state name s0 gt lt state name s1 gt lt state name s2 gt lt states gt lt transitions gt lt transition src s0 dst s0 label a gt lt transition src s0 dst s0 label b gt lt transition src s0 dst s1 label a gt lt transition src si dst s2 label b gt lt transition src s2 dst s2 label a gt lt transition src s2 dst s2 label b gt lt initial state s0 gt lt final state s2 gt lt transitions gt lt content gt lt automaton gt Usual shell indirections gt and lt can be used to combine TAF KIT commands For instance this is an easy means to bring a local copy of this file vcsn b dump automaton al gt al xml TAF KiT uses XML to exchange automata to get graphical rendering of the automaton you may either invoke dot dump and then use a Dot
6. exp Give the evaluation of exp against aut eval aut aut Evaluate the language described by the Boolean automaton aut2 on the transducer aut1 image aut Give an automaton that accepts all output produced by aut trim aut Trim transducer aut Algorithms for transducers sub normalize aut Give the sub normalized transducer of aut composition cover aut Outsplitting composition co cover aut Insplitting compose auti aut2 Compose auti1 and aut2 two sub normalized transducers u compose auti aut2 Compose auti and aut2 two Boolean transducers preserve the number of path to rt aut Give the equivalent realtime transducer of aut invert aut Give the inverse of aut intersection aut Transform a Boolean automaton in a fmp transducer by creating for each word a pair containing twice this word 15 b b Considered without weight B accepts words with a b With weights it counts the number of b s Figure 2 3 The automaton B 2 3 Z Automata This part shows the use of the program vcsn z but all comments should also stand for the programs vcsn z min plus and vcsn z max plus Again we will toy with some of the automata provided by vesn z see Section 3 2 2 3 1 Counting b s Let s consider B Figure 2 3 an N automaton i e an automaton whose label s weights are in N This time the evaluation of the word
7. initial 7 Set a state to be final 8 Set a state not to be final 9 Display the automaton in Dotty 10 Exit Your choice 1 10 If you enter 1 you will then be prompted for the number of states to add say 1 again The state O was created To make it initial select 5 and Your choice 1 10 5 For state 0 Likewise to make it final using choice 7 Finally let s add a transition Your choice 1 10 3 Add a transition from state 0 To state 0 Labeled by the expression atb The automaton is generalized that is to say rational expressions are valid labels On top of the interactive menu the current definition of the automaton is reported in a textual yet readable form Automaton description States 0 Initial states 0 Final states 0 Transitions 1 From 0 to O labeled by 1 a 1 b Interestingly enough states are numbered from 0 but transitions numbers start at 1 Also not that weights are reported although only 1 is valid for Boolean automata Finally hit 10 to save the resulting automaton in the file all xml 2 1 4 Rational expressions and Boolean automata VAUCANSON provides functions to manipulate rational expressions associated to Boolean au tomata This provides an alternative means to create automata vcsn b alphabet ab exp to aut atb gt all xml vcsn b dot dump all xml gt all dot 10 A 3 states 6 transitions 1 1 T 3 Minimizing This automat
8. 3 1 5 ladybird 6 A 6 states 21 transitions 1 1 T 1 3 2 Z Automata 3 2 1 bl A 2 states 5 transitions 1 1 T 1 21 3 2 2 cl 1 O lb GY a 2 b 1 y A 2 states 3 transitions I 1 T 1 3 3 Transducers 3 3 1 A 3 states 4 transitions 1 2 T 1 22
9. The VAUCANSON TAF KIT 1 0 User s Manual The VAUCANSON GROUP July 28th 2006 Contents Contents 1 1 Installation 3 LL Collie VAUCANSON lt lt discordia AA ee we oe ee bale 3 1 2 Building VAUCAMBON asa 444 dos ss de a ho de eee ES 3 2 The Vaucanson toolkit 4 2 1 Boolean automata lt c oo essa dal es A gun a a Be Rw 5 DL Fist Contacts o suis Bus Dial REA nan met du Ras eae 5 2 12 A first example isea 4 046 8 60 d du A dues hea 6 2 1 3 Interactive Definition of Automata 9 2 1 4 Rational expressions and Boolean automata 10 21 5 Available functions co occiso 12 A a ss ck e 4 Po MN ase ee net dns ere MUR oe ee so 14 DR D Lei hrs lime ER eae a ERIE Bie AR aS 14 222 Av lable EME i 2 2 HE HU k e le we EG has eS 15 T3 POI 0 dew dune SE ae AU RRR a ae de ODA EOS 16 Zool COMME UE 2 Leu Re ue see se RE Ge a 16 232 Available functions 4 24 66 4 4 4 ds dd da La do ose 4 de 17 3 Automaton Library 19 3 1 Boolean Automata 19 Halal GA sree Re A Ee a MR el IS Lane ED 19 ele WM sei ee ehh A Bae ad lora a Ge ae kh ee me a a 20 Sule GUARD Li 5 sida A ae ee ot ae Ba ol 20 SLA denbletel Las ss ea sus eM DAS RE 6 RAR ASA 20 SO BAD ew Se ee 8d ee oe ee ee eee E S ee ee Ea 21 E IN GR OE eee RS SS 21 A ML od sds Was che Di E De uen tes es we ene oe ee E 21 ee el a Oe a c
10. The function is the name of the operation to perform on the automaton specified as an XML file Some functions such as evaluation require additional arguments such as the word to evaluate Some others such as exp to aut do not have an automaton argument TAF KIT is made to work with Unix pipes that is to say chains of commands which feed each other Therefore all the functions produce a result on the standard output and if an automaton is then the standard input is used A typical line of commands from the TAF KIT reads as follows vcsn b determinize al xml gt aldet xml and should be understood or analyzed as follows 1 vesn b is the call to a shell command that will launch a VAUCANSON function vcsn b has 2 arguments the first one being the function which will be launched the second being the automaton that is the input argument of the function 2 determinize is as just said a VAUCANSON function And as it can easily be guessed determinize takes an automaton as argument performs the subset construction on it and outputs the result on the standard output 3 a1 xml is the description of an automaton of the automaton of Section 3 1 1 indeed in an XML format that is understood by VAUCANSON This file must exist before the line is executed The data automata directory provides a number of XML files for examples of automata a number of programs that produce the XML files for automata whose definition
11. ch depends on the type of the automaton Many users of automata consider only automata whose transitions are labeled by letters taken in an alphabet which we call roughly speaking classical automata or Boolean automata The first program of the TAF KIT vesn b allows to compute with classical automata and is described in Section 2 1 Section 2 2 describes the program vcsn tdc which allows to compute with transducers that is automata whose transitions are labeled by pair of words which are elements of a product of free monoids hence the name In Section 2 3 we consider the programs of the TAF KIT that compute with automata over a free monoid and with multiplicity or weight taken in the set of integers equipped with the usual operations of addition and multiplication that is the semiring Z It is planned that a forthcoming version will include also vesn zmin for automata over a free monoid with multiplicity in the semiring Z min vesn zmax for automata over a free monoid with multiplicity in the semiring Z max vcsn rw tdc for transducers viewed as automata over a free monoid with multiplicity in the semiring of rational sets or series over another free monoid 2 1 Boolean automata This section focuses on the program vcsn b the TAF KIT component dedicated to Boolean automata 2 1 1 First Contacts vcsn b and its peer components of TAF KIT all share the same simple interface vcsn b function automaton arguments
12. compliant program or use display that does both vcsn b dot dump al xml gt al dot A 3 states 6 transitions I 1 T 1 Determinization of A To determinize a Boolean automaton call the determinize function vcsn b dump automaton al vcsn b determinize gt aldet xml To get information about an automaton call the info function vcsn b info aldet xml States 4 Transitions 8 Initial states 1 Final states 2 Or use dotty to visualize it vcsn b dot dump aldet xml gt aldet dot A 4 states 8 transitions I 1 T 2 Evaluation To evaluate whether a word is accepted vcsn b eval ai xml abab 1 vcsn b eval al xml bbba 0 where 1 resp 0 means that the word is accepted resp not accepted by the automaton 2 1 3 Interactive Definition of Automata TAF KIT provides a text interface to define automata interactively rather than having to deal with XML files Two functions are available define automaton to build a fresh automaton from scratch edit automaton to modify an existing automaton The interface is based on a menu of choices vcsn b alphabet ab define automaton all xml Automaton description States none Initial states none Final states none Transitions none Please choose your action 1 Add states 2 Delete a state 3 Add a transition 4 Delete a transition 5 Set a state to be initial 6 Set a state not to be
13. depend upon some variables and the TAF KIT itself allows to define automata and thus to produce the corresponding XML files cf below 4 gt aldet xml puts the result of determinize into the file a1 xml that is the XML file which describes the determinized automaton of Aj As a more elaborate example consider the following command vcsn b dump automaton al vcsn b determinize vcsn b minimize vcsn b info States 3 Transitions 6 Initial states 1 Final states 1 It fetches the automaton ai from the automaton library determinizes it minimizes the result and finally displays information about the resulting automaton Please note the typographic conventions user input is represented like this standard output follows like this followed by standard error output error like this and finally if different from 0 the exit status is represented gt like this For instance lThis format is not exactly part of the VAUCANSON platform It has been developed for providing a means of communication between various programs dealing with automata And then it has been used as a communication tool between the invocations of VAUCANSON function by the TAF KIT A lay user of the TAF KIT should not need to know how this format is defined vcsn b dump automaton al vcsn z info error invalid semiring B expected Z gt 1 Other than that the interface of the TAF Krr components is usual including options
14. h ake te Fe et A te ee Fe A 22 Bay JPA 4 LU La we Re LA RR MAR Oe a ee ee Kae 22 ee TL Gaia ae ee eH ay a ee AI 22 Gene lesa ORDERED RAR o ha ED DE 22 Introduction The VAUCANSON software platform is dedicated to the computation with finite state automata Here finite state automata is to be understood in the broadest sense weighted automata on a free monoid that is automata that not only accept or recognize words but compute for every word a multiplicity which is taken a priori in an arbitrary semiring and even weighted automata on non free monoids The latter become far too general objects As for now are implemented in VAUCANSON only the weighted automata on direct products of free monoids machines that are often called transducers that is automata that realize weighted relations between words When designing VAUCANSON we had three main goals in mind we wanted 1 a general purpose software 2 a software that allows a programming style natural to computer scientists who work with automata and transducers 3 an open and free software This is the reason why we implemented so to say on top of the VAUCANSON platform a library that allows to apply a number of functions on automata and even to define and edit automata without having to bother with subtleties of C programming The drawback of this is obviously that the user is given a fixed set of functions that apply to already typed automata This
15. library of functions does not allow to write new algorithms on automata but permits to combine or compose without much difficulties nor efforts a rather large set of commands We call it TAF KIT standing for Typed Automata Function Kit as these commands take as input and output automata whose type is fixed TAF KIT is presented in Chapter 2 When the relation is weighted the multiplicity has to be taken in a commutative semiring Chapter 1 Installation 1 1 Getting Vaucanson The latest stable version of the VAUCANSON platform can be downloaded from http vaucanson 1lrde epita fr The current development version can be retrieved from its Subversion repository as follows svn checkout https svn lrde epita fr svn vaucanson trunk vaucanson 1 2 Building Vaucanson The following commands build and install the platform cd vaucanson 1 0 Then configure di malo 4 aude make install More detailed information is provided in the files INSTALL which is generic to all packages using the GNU Build System and README which details VAUCANSON s specific build process Subversion can be found at http subversion tigris org Chapter 2 The Vaucanson toolkit This chapter presents a simple interface to VAUCANSON a set of programs tailored to be used from a traditional shell Since they exchange typed XML files there is one program per automaton type Each program supports a set of operations whi
16. nd aut2 are isomorphic eval aut word Evaluate word on aut is ambiguous aut Return whether aut is ambiguous is complete aut Return whether aut is complete is deterministic aut Return whether aut is deterministic is empty aut Return whether trimed aut is empty is realtime aut Return whether aut is realtime is standard aut Return whether aut is standard Generic algorithms for automata accessible aut Give the maximal accessible subautomaton of aut eps removal aut Give aut closed over epsilon transitions eps removal sp aut Give aut closed over epsilon transitions co accessible aut Give the maximal coaccessible subautomaton of aut 12 complete aut Give the complete version of aut concatenate auti aut2 Concatenate auti and aut2 power aut n Give the power of aut by n product auti aut2 Give the product of auti by aut2 quotient aut Give the quotient of aut realtime aut Give the realtime version of aut standardize aut Give the standard automaton of aut union of standard auti aut2 Give the union of standard automata concat of standard auti aut2 Give the concatenation of standard automata star of standard aut Give the star of automaton aut sum auti aut2 Give the sum of auti and aut2 transpose aut Transpose the automaton aut
17. on constructed following the Thompson algorithm is not the simplest one it can be minimized vcsn b minimize all xml gt allmin xml vcsn b dot dump allmin xml gt allmin dot A 3 states 6 transitions 1 1 T 3 Computing the language recognized by a Boolean automaton can be done using aut to exp vcsn b aut to exp all xml b a ax b a a x b b x a a 1 a ax 1 vcsn b aut to exp allmin xml b a ax b a a b b x a a 1 a ax 1 11 VAUCANSON provides several algorithms that build an automaton that recognizes a given language The following sequence computes the minimal automaton of a b ab a b vcsn b alphabet ab standard a b a b a b vcsn b minimize gt 11 xml vcsn b dot dump 11 xml gt 11 dot A 3 states 6 transitions I 1 T 1 2 1 5 Available functions The whole list of supported commands is available via list commands vcsn b list commands List of available commands Input output work define automaton file Define an automaton from scratch display aut Display aut dot dump aut Dump dot output of aut dump automaton file Dump a predefined automaton edit automaton file Edit an existing automaton identity aut Return aut info aut Print useful infos about aut list automata List predefined automata Tests and evaluation on automata are isomorphic auti aut2 Return whether auti a
18. such as version and help vcsn b help Usage lt vcsn b OPTION lt command gt lt args gt VCSN TAF Kit a toolkit for working with automata a alphabet ALPHABET Set the working alphabet for rational expressions B bench NB_ITERATIONS Bench l list commands List the commands handled by the program 0 bench plot output OUTPUT_FILENAME Bench output filename T report time Report time statistics v verbose Be more verbose print boolean results The following alphabets are predefined ascii Use all the ascii table as the alphabet 1 as epsilon a z Use a z as the alphabet 1 as epsilon a zA Z Use a zA Z as the alphabet 1 as epsilon ab Use ab as the alphabet 1 as epsilon help Give this help list usage Give a short usage message V version Print program version Mandatory or optional arguments to long options are also mandatory or optional for any corresponding short options Report bugs to lt vaucanson bugs lrde epita fr gt The whole list of supported commands is available via list commands 2 1 2 A first example VAUCANSON provides a set of common automata The function list automata lists them all vcsn b list automata The following automata are predefined al bi div3base2 double 3 1 ladybird 6 Let s consider the Boolean automaton A Figure 2 1 part of the standard library It can be dumped using dump
19. w by the automaton B will produce a number rather than simply accept or reject w For instance let s evaluate abab and bbab vcsn z dump automaton b1 vcsn z eval abbb 3 vcsn z dump automaton b1 vcsn z eval abab 2 Indeed B counts the number of b s Power Now let s consider the BY where n T Il B n gt 0 i 1 This is implemented by the power function vcsn z dump automaton b1 vcsn z power 4 gt b4 xml vcsn z power bi xml 4 gt b4 xml The file b4 xm1 now contains the automaton Bf Let s check that the evaluation of the words abab and bbab by Bf gives the fourth power of their evaluation by By vcsn z eval b4 xml abbb 81 vcsn z eval b4 xml abab 16 16 Quotient Successive products of an automaton create a lot of new states and transitions vcsn z dump automaton b1 vesn z info States 2 Transitions 5 Initial states 1 Final states 1 vcsn z info b4 xml States 16 Transitions 97 Initial states 1 Final states 1 One way of reducing the size of our automaton is to use the quotient algorithm vcsn z quotient b4 xml vcsn z info States 5 Transitions 15 Initial states 1 Final states 1 2 3 2 Available functions In this section you will find a brief definition of all functions for manipulating weighted automata The following functions are available for both They are called using vcsn z vcsn z max plus
Download Pdf Manuals
Related Search