The Vaucanson TAF-Kit 1.2.93 User's Manual - LRDE
Contents
1. 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 au tomata The following functions are available for both They are called using vcsn char z vcsn char z max plus and vcsn char z min plus run as program algorithm name arguments vcsn char 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 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 aut is empty has succ comp aut Return whether aut has successful computations trimmed aut is not 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 aut2. 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 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 O 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 0 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 char b alphabet ab exp to aut
3. Give the evaluation of exp against aut eval aut auti aut2 Evaluate the language described by the Boolean automaton aut2 on the transducer aut1 1tl to pair aut Give an automaton defined over a pair letter alphabet same as aut image aut Give an automaton that accepts all output produced by aut transpose aut Give the transposed of the transducer aut trim aut Trim transducer aut Algorithms for transducers sub normalize aut Give the sub normalized transducer of aut composition cover aut Dutsplitting 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 transducers preserve the number of paths to rw aut Give the equivalent rational weight transducer of aut 18 invert aut Give the inverse of aut intersection aut Transform a Boolean automaton into an fmp transducer by creating for each word a pair containing twice this word 19 b b Considered without weight Bj accepts words with a b With weights it counts the number of b s Figure 2 3 The automaton Bj 2 3 Z Automata This part shows the use of the program vcsn char z but all comments should also stand for the programs vcsn char z min plus and vcsn char z max plus Again we will toy with some of the automata provided by vcsn char z see Se
4. Give aut closed over epsilon transitions co accessible aut Give the maximal coaccessible subautomaton of aut complete aut Give the complete version of aut 21 concatenate auti aut2 Concatenate aut1 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 aut1 aut2 Give the concatenation of standard automata star of standard aut Give the star of automaton aut union auti aut2 Give the union 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 expand exp Expand exp identity exp exp Output exp after trivial simplifications standard exp Give the standard automaton of exp thompson exp Give the Thompson automaton of exp exp 22 Chapter 3 Automaton Library VAUCANSON comes with a set of interesting automata that can be used to toy with TAF KIT Chapter 2 for
5. a b gt a11 xml vcsn char b dot dump all xml gt all dot 11 A 3 states 6 transitions 1 1 T 3 2 1 5 Token representations When dealing with rational expressions in TAF KIT one may be willing to for example change the representation of the epsilon More generally the rational expressions parser understand 10 such tokens They are e OPAR the opening association parenthesis e CPAR the closing association parenthesis e PLUS the semi ring additive law e TIMES the monoid concatenation law e STAR the Kleene star e ONE the identity of the monoid e ZERO the zero of the semi ring e OWEIGHT the opening weight brace e CWEIGHT the closing weight brace e SPACE a whitespace character Each token must be a non empty string with arbitrary length Some checks will be done by TAF KIT to ensure tokens do not collide You can also use the ALPHABET token an arbitrary number of times to append letters to the current alphabet The following commands vcsn char b alphabet ab exp to aut a b gt parser xml vcsn char b dot dump parser xml gt parser dot 12 A 3 states 6 transitions 1 1 T 3 will give the same results as vcsn char b alphabet a parser ALPHABET b ONE e STAR star exp to aut a b star gt parser2 x vcsn char b dot dump parser2 xml gt parser2 dot A 3 states 6 transitions 1 1 T 3 With the ALPHABET token you
6. can specify two types of letters e letters one character is used to represent a letter e words many characters are used to represent a letter For example ALPHABET letters abc defines the alphabet with three letters a b c while ALPHABET words abc defines the alphabet with only one letter abc Letters are separated by commas and each TAF KTtT context defaults to either letters vesn char b eg or words vesn int b eg vesn int b alphabet 0 1 2 3 4 5 6 7 8 9 and vcsn int b alphabet letters 0123456789 will give the same alphabets 13 Everywhere you want to use special characters used by the parser option prepending a backslash character will escape it So you can write ALPHABET X which defines the alphabet with the two letters and Finally whenever you may put a single character you may write a pair a words The following construction is then valid ALPHABET and defines the alphabet with only one letter the pair whose first component is and the second one is For more details the grammar of the parser option is included in the source code in EBNF notations Minimizing This automaton constructed following the Thompson algorithm is not the simplest one it can be minimized vcsn char b minimize all xml gt allmin xml vcsn char 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 don
7. 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 char 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 char b dump automaton al vcsn char b determinize gt aldet xml To get information about an automaton call the info function vcsn char b info aldet xml States 4 Transitions 8 Initial states 1 Final states 2 Or use dotty to visualize it vcsn char b dot dump aldet xml gt aldet dot A 4 states 8 transitions HI 1 T 2 Evaluation To evaluate whether a word is accepted vcsn char b eval al xml abab 1 vcsn char 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 char b alphabet ab define automaton all xml Automaton description States none Initial states none Final states none Transitions none Please choose your action 10
8. The VAUCANSON TAF KIT 1 2 93 User s Manual The VAUCANSON GROUP 2008 10 09 Contents Contents 1 Installation 1 1 Getting VAUCANSON 1 2 Building VAUCANSON 2 The Vaucanson toolkit 2 1 Boolean automatas 21 1 First Contacts o sa sew a a data Ro A a at ds ds a A 2 1 2 A first example oo i ae eek ra A oe aes 2 1 3 Interactive Definition of Automata 0 0 0 0 0000000008 2 1 4 Rational expressions and Boolean automata 2 1 5 Token representations os osoo a 2 16 Available functions s aE a e ee es 2 2 Transducers rice e iri aa a E gie a a Laa E haa oaar aa 2 2 1 Example s s sa aaa aa a a aA a ek aed 2 2 2 Available functions 2 3 Z Automata 0 sc osas ee RA ae A owe eA 2 9 1 OOUNtING bds errs YA aP de ee OR Ye ee hs Hae 2 3 2 Available functions 2 2 a a a 3 Automaton Library 3 1 Boolean Automata s s e ee Solel ale arse te E SLA Pl eh bah ed Ba oth whee Gye Dd amp Ba hah we bs dad a de Bd 3 1 3 div3 based cn 4 44 8a Ab ae wee DR oe Da ee Eee Ra RAS 3 1 4 double a wae a A a a A DR a RE 3 1 5 ladybirds6 wu s Dop oa a Saree Be dee ee a ee a Oe ee A 3 2 Z Automatal ostra da a ee a A a S2 ADI he Be
9. ary 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 1rde 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 2 93 Then configure dnd de ide 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
10. c is empty aut Return whether aut is empty has succ comp aut Return whether aut has successful computations trimmed aut is not 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 concatenate autl 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 15 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 aut1 aut2 Give the concatenation of standard automata star of standard aut Give the star of automaton aut union auti aut2 Give the union 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 de
11. ction 3 21 2 3 1 Counting b s Let s consider 6 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 B will produce a number rather than simply accept or reject w For instance let s evaluate abab and bbab vcsn char z dump automaton b1 vcsn char z eval abbb 3 vcsn char z dump automaton b1 vcsn char z eval abab 2 Indeed B counts the number of b s Power Now let s consider the 57 where n Il B n gt 0 i 1 This is implemented by the power function vcsn char z dump automaton b1 vcsn char z power 4 gt b4 xml vcsn char 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 By vcsn char z eval b4 xml abbb 81 vcsn char z eval b4 xml abab 16 20 Quotient Successive products of an automaton create a lot of new states and transitions vcsn char z dump automaton b1 vcsn char z info States 2 Transitions 5 Initial states 1 Final states 1 vcsn char 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 char z quotient b4 xml vcsn char z info States 5 Transitions 15
12. e using aut to exp vcsn char b aut to exp all xml a a btb a a b tb a axt1 1 a a vcsn char b aut to exp allmin xml a a btb a a bt tb a axt1 ta a 1 VAUCANSON provides several algorithms that build an automaton that recognizes a given language The following sequence computes the minimal automaton of a b ab atb vcsn char b alphabet ab standard atb a b atb vcsn char b quotient gt 11 xml vcsn char b dot dump 11 xml gt 11 dot 14 la b 1 v A 3 states 6 transitions 1 1 T 1 2 1 6 Available functions The whole list of supported commands is available via list commands vcsn char 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 equivalent auti aut2 Do Aut1 and Aut2 recognize the same language 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 deterministi
13. ee pete tee A a ee ae o ei Se Ge oe ee eS Mon te a Es ay dai po 3 3 Boolean FMP Transducers E E A LAU aaa en aa aa a a ee a a A a SAA ww w 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 libr
14. igits Use 0 9 as the alphabet 1 as epsilon ascii Use ascii characters 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 char b list automata The following automata are predefined al bi div3base2 double 3 1 ladybird 6 b b The graphical layout of this automaton was described by hand using the Vaucanson G TEX 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 Let s consider the Boolean automaton A Figure 2 1 part of the standard library It can be dumped using dump automaton vcsn char b dump automaton al lt fsmxml xmlns http vaucanson lrde epita fr version 1 0 gt lt automaton gt lt valueType gt lt semiring operations classical set B type numerical gt lt monoid genDescrip enum genKind simple genSort letters type free gt lt monGen value a gt lt monGen value b gt lt monoid gt lt valueType gt
15. 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 23 3 1 2 bl 1 vy A 2 states 5 transitions 1 1 T 1 3 1 3 div3base2 A 3 states 6 transitions 1 1 T 1 3 1 4 double 3 1 A 3 states 6 transitions 1 1 T 1 24 3 1 5 ladybird 6 A 6 states 21 transitions 1 1 T 1 3 2 Z Automata 3 2 1 bl 1 OS b Of 1 vy A 2 states 5 transitions I 1 T 1 25 3 2 2 cl ox b Onn a 2 b 1 v A 2 states 3 transitions 1 1 T 1 3 3 Boolean FMP Transducers 3 3 1 t1 A 3 states 4 transitions I 1 T 2 3 3 2 ul A 3 states 4 transitions I 2 T 1 26
16. lt automatonStruct gt lt states gt lt state id s0 gt lt state id s1 gt lt state id s2 gt lt states gt lt transitions gt lt transition src s2 target s2 gt lt label gt lt monElmt gt lt monGen value b gt lt monElmt gt lt label gt lt transition gt lt transition src s2 target s2 gt lt label gt lt monElmt gt lt monGen value a gt lt monElmt gt lt label gt lt transition gt lt transition src si target s2 gt lt label gt lt monElmt gt lt monGen value b gt lt monElmt gt lt label gt lt transition gt lt transition src s0 target s0 gt lt label gt lt monElmt gt lt monGen value b gt lt monElmt gt lt label gt lt transition gt lt transition src s0 target s1 gt lt label gt lt monElmt gt lt monGen value a gt lt monElmt gt lt label gt lt transition gt lt transition src s0 target s0 gt lt label gt lt monElmt gt lt monGen value a gt lt monElmt gt lt label gt lt transition gt lt initial state s0 gt lt final state s2 gt lt transitions gt lt automatonStruct gt lt automaton gt lt fsmxml gt Usual shell indirections gt and lt can be used to combine TAF KIT commands For y instance this is an easy means to bring a local copy of this file vcsn char b dump automaton al gt al xml TAF KiT uses XML to exchange automata to
17. lt 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 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 aldet xml that is the XML file which describes the determinized automaton of A As a more elaborate example consider the following command vcsn char b dump automaton al vcsn char b determinize vcsn char b minimize vcsn char b i States 3 Transitions 6 Initial states 1 Final states 1 It fetches the automaton al 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 means of communicatio
18. n 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 Krr A lay user of the TAF KiT should not need to know how this format is defined vcsn char b dump automaton al vcsn char b info States 3 Transitions 6 Initial states 1 Final states 1 Other than that the interface of the TAF KIT components is usual including options such as version and help vcsn char b help Usage lt vcsn char b OPTION lt command gt lt args gt VCSN TAF Kit a toolkit for working with automata a alphabet ALPHABET Set the alphabet for rational expressions or automata B bench NB_ITERATIONS Bench D export time dot VERBOSE_DEGREE Export time statistics in DOT format i input type INPUT_TYPE Automaton input type FSM or XML 1 list commands List the commands handled by the program o output type 0UTPUT_TYPE Automaton input type FSM XML or DOT 0 bench plot output 0UTPUT_FILENAME Bench output filename p parser 0PTIONS Set the parsing options for rational expressions T report time VERBOSE_DEGREE Report time statistics v verbose Be more verbose print boolean results X export time xml Export time statistics in XML format The following alphabets are predefined letters Use a z as the alphabet 1 as epsilon alpha Use a zA Z as the alphabet 1 as epsilon d
19. on t1 vcsn char fmp b alphabeti ab domain gt div by 3 xml Figure 2 2 and part of the automaton 3 Now the file divisible by 3 xml contains the description of a Boolean automaton that accepts only the numbers divisible by 3 vcsn char b dot dump div by 3 xml gt div by 3 dot dif A 3 states 4 transitions I 1 T 2 2 2 2 Available functions The following functions are available for both vcsn char rw and vcsn char fmp b programs To invoke them run program algorithm name arguments vcsn char fmp 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 transducers is empty aut Return whether aut is empty has succ comp aut Return whether aut has successful computations trimmed aut is not empty 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 exp
20. onoid 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 char b the TAF KIT component dedicated to Boolean automata 2 1 1 First Contacts vcsn char b and its peer components of TAF KIT all share the same simple interface vcsn char 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 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 char b determinize al xml gt aldet xml and should be understood or analyzed as follows 1 vcsn char b is the call to a shell command that will launch a VAUCANSON function vcsn char 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 resu
21. 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 we call roughly speaking classical automata or Boolean automata The first program of the TAF KIT vcsn char b allows to compute with classical automata and is described in Section 2 1 A variant of this program called vcsn int b handles Boolean automata whose letters are integers Section 2 2 describes the program vcsn char fmp b 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 A variant of this program called vcsn int fmp b handles transducers whose letters are integers 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 A variant of this program called vcsn int z is specialized to handle Z automata whose letters are integers It is planned that a forthcoming version will include also vesn char zmin for automata over a free monoid with multiplicity in the semiring Z min vesn char zmax for automata over a free monoid with multiplicity in the semiring Z max vesn char rw for transducers viewed as automata over a free m
22. terminized 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 identity exp exp Output exp after trivial simplifications standard exp Give the standard automaton of exp thompson exp Give the Thompson automaton of exp exp 16 0 0 1 1 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 Krr only pro vides one view vesn char fmp b considering a transducer as a weighted automaton of a product of free monoid In a forthcoming release TAF Krr will provide vesn char rw 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 library Section 3 3 1 Domain The transducer T only accepts binary numbers divisible by vcsn char fmp b dump automat
Download Pdf Manuals
Related Search