The new automaton accepts a word if and only if is identical to a concatenation of two words w1w2, where w1 is accepted by the first input automaton and w2 by the second. An new automaton with the same alphabet is computed and output.
Two finite state automata, which must have the same alphabet, are read in from the files filename1 and filename2. Output is to file3 if three filenames are specified and to stdout otherwise fsaconcatįsaconcat filename1 filename2 output_file Presumably because of this, and bcause this is almost the only practical use made of this operation, the KBMAG version of this utility is called gpcomp, but the method of construction is in principle applicable to any two two- variable FSA, not just multipliers, and could, for example, be used to help verify whether some FSA that purported to encode a total order of the words in the alphabet actually did so. If the input automata were the multipliers for words w1 and w2 respectively in some group or coset system, then the output automaton is the multiplier for the word w1w2. The output automaton is a two variable FSA that accepts a word pair (u,v) if and only if there is some w such that the first automaton accepts (u,w) and and the second automaton accepts (w,v). A new finite state automaton is computed, minimised, and output. Two finite state automata are read in, which should both be two-variable automata using the same alphabet. Output is to file3 if three filenames are specified and to stdout otherwise fsacompose fsacompose file1 file2 file3 If the input automata were word acceptors for two groups, the output automaton is in effect the word acceptor for the direct product of the two groups. The accepted language is therefore the cartesian product of the two input languages. The output automaton is a two variable FSA that accepts a word pair (u,v) if and only if the first automaton accepts u and the second automaton accepts v. Two finite state automata are read in, which should both be single-variable automata using the same alphabet. fsacartesian fsacartesian file1 file2 file3 The default output filename is input_file.bfs.
In fact this is exactly what fsalequal does. If they have the same language, then the resulting automata should be identical. fsamin and fsabfs used together can be used to check whether two deterministic automata with the same alphabet have the same language. , n, and if oneĮxamines the transition-table, in order of increasing states, then the states first occur in sequence. This means that the states are numbered 1,2. fsabfs fsabfs -i | input_file Ī finite state automaton is read in, and then its states are permuted into bfs-order (bfs = breadth-first-search), and it is printed out again. In fact the internal equivalent of the option is used to limit the size of the output language. Indeed, this is more or less how automata constructs the word acceptor and general multiplier for an automatic group. If not then one submits some of its accepted words to some error correcting code. The aim is for the "and not" automaton to have an empty language. The general method of proceeding is to first construct a candidate automaton, then to construct a candidate two-variable automaton which should accept (w,op(w)), then form the "exists" automaton of this and then combine it with the candidate automaton using and_not. "and not" automata are very often useful where one is trying to construct an automaton whose language should be closed under some operation. The option modifies the language of the output automaton in the following way: The output automaton accepts a word w if the first accepts w but the second does not, and no prefix of w was accepted by the first and rejected by the second. The output automaton accepts a word w if and only if the first input automaton accepts w but the second input automaton does not. The option modifies the language of the output automaton in the following way: The output automaton accepts a word w if both input automata accept it, and no prefix of w was accepted by both automata (so that any accepting state is also final). An automaton that accepts a word w in the alphabet if and only if both of the input automata accept w is computed, minimised, and output. You may like to note that here and elsewhere the author has used the abbreviation FSA to refer to a single finite state automaton, and the abbreviation FSAs for the plural, despite his classical education. In this section, we describe the utilities that are provided for manipulating finite state automata. MAF Programs for Manipulating Finite State Automata MAF Programs for Manipulating Finite State Automata
0 kommentar(er)
