The Vaucanson TAF-Kit 1.0 User`s Manual - LRDE
Contents
1. a toolkit for working with automata a alphabet ALPHABET Set the working alphabet for rational expressions l list commands List the commands handled by the program 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 automaton vcsn b dump automaton al lt automaton name ai xmlns http vaucanson lrde epita fr gt lt labelType gt lt monoid generators letters type free gt lt generator value a gt lt generator value b gt lt monoid gt lt semiring operation2. 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 15 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 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 stardard expand exp Expand exp standard exp Give the standard automaton of thompson exp Give the Thompson automaton of 16 exp exp exp Chapter 3 Automaton Library VAUCANSON comes with a set of interesting automata that can be used to toy with TAF Krr 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 I 1 T 1 17 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 18 3 1 5 ladybird 6 A 6 states 21 transitions 1 1 T
3. 1 3 2 Z Automata 3 2 1 bl A 2 states 5 transitions I 1 T 1 19 3 2 2 cl 1 O b GD a 2 b 1 y A 2 states 3 transitions I 1 T 1 3 3 Transducers 3 3 1 tl A 3 states 4 transitions 1 1 T 2 3 3 2 ul A 3 states 4 transitions 1 2 T 1 20
4. ee HY 20 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 library of functions does not allow to write new algorithms on automata but permits to combine or compose without much difficulties nor efforts a rath
5. files cf below 4 gt aidet xml puts the result of determinize ai xml that is the XML file which describes the determinized automaton of A into the file aldet xml1 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 1This format is not exactly part of the VAUCANSON platform It has been developed for providing a mean of communication between various programs dealing with automata And then it has been used as a communication tool between the invocation 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 Bad semiring gt 1 Other than that the interface of the TAF KIT components is usual including options such as version and help vcsn b help Usage vcsn b OPTION lt command gt lt args gt VCSN TAF Kit
6. 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 vesn 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 The function is the name of the operation to perform on the automaton specified as an XML file Some functions such as evaluation will require additiona
7. The VAUCANSON TAF KIT 1 0 User s Manual The VAUCANSON GROUP July 28th 2006 Contents Contents 1 1 Installation 3 11 Secting VAUCANSON o LE as eee ad DE eR a 4e ee be 3 1 2 Building VAUCANSON sos ea ec ase eee ee a a 3 2 The Vaucanson toolkit 4 21 Boolean automata c LE Les da 8806 ee ee dae de aa a E a e Rip 5 SLA First Contacig o ioa pas dead we RRA arr dans a a a 5 2 12 rest example eco ios ii 8 4 4 ana hi au bu 6 2 1 3 Rational expressions and Boolean automata 10 214 Available functions o sees erya cion ds us dau ee ee ad 11 Boe bi e 22 ek da a ae Sun tat OS ml ns kh ES ee 12 22 EXA oc baie G8 be a ao Ee ee pee a a 12 222 Available functions 4 4 4 6440 08 oc eae dae ee GO GS Ree RS de 13 SE wD Go eS 14 Zack Cpuming MS peer be ER ewe DS eee eEAG 14 20 2 Available foncti ns pra ee ee 6 ed de es 15 3 Automaton Library 17 ol Boolean Automata o ne saa eea we RR e eh Ee we De OS 17 LE TE on aye ea E ee GO De 17 SA Blois dae Dan A oh ete ee ta ae See E 18 313 APS arcada OE OA Ree Eee Sed EEE oS 18 ola duel Lo si ni ee AR ue Buse as be eh BE eR ESS 18 316 Tadyhwd ora bea eee e de eae DEGREES Es du 19 D LAMON 2 2e Oe le Ra de ed eue ee ee a e aeea A 19 Pee We a a A vom et ag hier 19 TEE ss ton vst He a nd tes wat tov ve acct eh a tbs de de Be eats re 20 moe o IEA 20 Rel Maa a o o aid dt nd AA 20 Bee Mc a a a a ee a
8. coming 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 The transducer T only accepts binary numbers divisible by 3 vcsn tdc dump automaton t1 vesn 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 12 A 3 states 4 transitions 1 1 T 2 2 2 2 Available functions The following functions are available for both vcsn rw tdc and vcsn tdc programs To invoke them run program algorithm name arguments vcesn 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 isomor
9. er 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 lrde epita fr The current development version can be retrieved from its Subversion reposi tory 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 make sudo 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 which 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
10. l arguments such as the word to evaluate Some other functions 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 ai 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 Which means that 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 depend upon some variables and the TAF KIT itself allow to define automata and thus to produce the corresponding XML
11. n 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 Minimizing The minimal automaton can be computed the same way vcsn b minimize aldet xml gt aldetmin xml vcsn b dot dump aldet xml gt aldetmin dot A 4 states 8 transitions 4I 1 T 2 The commands can be composed with pipes from the shell using to denote the standard input vcsn_b determinize al xml vcsn_b minimize gt al_min xml Evaluation To evaluate whether a word is accepted vcsn b eval al 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 Rational expressions and Boolean automata VAUCANSON provides functions to manipulate rational expressions associated to Boolean au tomata For instance computing the language recognized by a Boolean automaton can be done using aut to exp vcsn b aut to exp al xml atb a b atb vcsn b aut to exp aldet xml b a a b a a b b a ax 1 VAUCANSON provides several algorithms that build an automaton that recognizes a given language The following sequence computes the minimal automaton of at b ab atb vcsn b alphabe
12. phic auti aut2 Test if aut1 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 domain aut Give the automaton that accepts all inputs accepted by aut eval aut 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 auti 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 intersection aut Transform a Boolean automaton in a fmp transducer by creating for each word a pair containing twice this word 13 b b Considered without weight B1 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 s
13. s numerical set B gt The graphical layout of this automaton was described by hand using the Vaucanson G LTEX package However the following figures are generated by TAF KIT giving a b very nice layout yet slightly less artistic Figure 2 1 The automaton A 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 si 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 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 KtT uses XML to exchange automata to get graphical rendering of the automaton you may either invoke dot dump and then use a Dot compliant program or use display that does both vcsn b dot dump al xml gt al dot A 3 states 6 transitions 1 1 T 1 Determinization of A To determinize a Boolean automaton call the determinize function vcsn b dump automaton al vcs
14. sion 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 aut1 by aut2 quotient aut Give the quotient of aut realtime aut Give the realtime version of aut sum auti aut2 Give the sum of auti and aut2 transpose aut Transpose the automaton aut 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 stardard exp expand exp Expand exp standard exp Give the standard automaton of exp thompson exp Give the Thompson automaton of exp 11 010 ql The transducer computing the quotient by 3 of a binary number Figure 2 2 Rational weight transducer 71 2 2 Transducers While the VAUCANSON library supports two views of transducers currently TAF KIT only pro vides one view vesn tde considering a transducer as a weighted automaton of a product of free monoid In a forth
15. t ab standard atb a b atb vcsn b minimize gt 11 xml vcsn b dot dump 11 xml gt 11 dot 3 O S o A 3 states 6 transitions 1 1 T 1 2 1 4 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 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 deterministic aut Return whether aut is deterministic is empty aut Return whether trimed aut is empty is realtime aut Return whether aut is realtime Generic algorithms for automata accessible aut Give the maximal accessible subautomaton of aut eps removal aut Give aut closed over epsilon transitions co accessible aut Give the maximal coaccessible subautomaton of aut complete aut Give the complete ver
16. tand for the programs vcsn z min plus and vcsn z max plus Again we will toy with some of the automata provided by vcsn 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 w by the automaton 6 will produce a number rather than simply accept or reject w For instance let s evaluate abab and bbab vcsn z dump automaton bi vcsn z eval abbb 3 vcsn z dump automaton bi vcsn z eval abab 2 Indeed B counts the number of b s Power Now let s consider the BY where n A II 5 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 b1 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 Bi vcsn z eval b4 xml abbb 81 vcsn z eval b4 xml abab 16 14 Quotient Successive products of an automaton create a lot of new states and transitions vcsn z dump automaton b1 vcsn 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
17. 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 and vcsn z min plus run as program algorithm name arguments vesn 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 Generic algorithms for automata accessible aut Give the maximal accessible subautomaton of aut eps removal aut Give aut closed over epsilon transitions co accessible aut Give the maximal coaccessible subautomaton of aut
Download Pdf Manuals
Related Search