The KBMag package contains GAP interfaces to many of the functions for manipulating finite state automata (fsa) that are available in the stand-alone. We shall list these here, without giving much detail. For more detail, the user could try looking in the source file gap/fsa4.g.
fsa are currently implemented as GAP records, as they were previously in GAP3. This interface may be updated to the style of GAP4 at some stage. (Note that the abbreviation fsa will be used for both singular and the plural.)
The alphabet of an fsa is itself a record that must contain at least the two components type and size, where type is a string, and size a positive integer. The easiest possibility is to use the type simple, and then no other record components are necessary. There are several more complicated possibilities, which are used by the other rewriting system functions. For example, there is the type identifiers, for which fields format and names are necessary. For example:
gap> M := FreeMonoid( 3 );; gap> alph := rec( type := "identifiers", size := 3, > format := "dense", names := [M.1,M.2,M.3] );;
defines a valid alphabet for an fsa. The members of the alphabet are referred to as letters, and can be represented either by a positive integer or by their name (usually a generator of a free group or monoid) if they have one.
The functions ReductionAutomaton (2.5-2), WordAcceptor (2.6-2), FirstWordDifferenceAutomaton (2.6-2), SecondWordDifferenceAutomaton (2.6-2) and GeneralMultiplier (2.6-2) mentioned in earlier sections all return a fsa. The other possibilities for the user to construct a fsa are to use the function FSA (4.1-3) or to read one in from a file. In the latter case, the user must immediately call InitializeFSA (4.1-2) on the record that has been read in. For example, running GAP from the package directory:
gap> Read( "standalone/fsa_data/fsa_2" ); gap> InitializeFSA( fsa_2 );
‣ IsInitializedFSA( fsa ) | ( function ) |
Tests whether fsa is a record describing a valid initialized fsa.
‣ InitializeFSA( fsa ) | ( function ) |
Initializes a record representing a fsa that has been read in from a file.
‣ FSA( alph ) | ( function ) |
Returns an initialized fsa with alphabet alph having one state that is an initial and final state, and no transitions (edges).
The arguments of the following functions must be initialized fsa.
‣ WriteFSA( fsa ) | ( function ) |
Displays fsa nicely. (In a proper implementation, this would be the ViewObj function.)
‣ IsDeterministicFSA( fsa ) | ( function ) |
Tests whether fsa is a deterministic fsa. Many of the functions below work only for deterministic fsa. A deterministic fsa with the same language as fsa can be constructed with the function DeterminizeFSA (4.2-1).
‣ AlphabetFSA( fsa ) | ( function ) |
‣ StatesFSA( fsa ) | ( function ) |
Return, respectively, the records representing the alphabet and state-set of fsa.
‣ NumberOfStatesFSA( fsa ) | ( function ) |
Returns the number of states of fsa.
‣ NumberOfLettersFSA( fsa ) | ( function ) |
‣ SizeOfAlphabetFSA( fsa ) | ( function ) |
Returns the size of the alphabet of fsa.
‣ AcceptingStatesFSA( fsa ) | ( function ) |
Returns the list of accepting states of fsa.
‣ InitialStatesFSA( fsa ) | ( function ) |
Returns the list of initial states of fsa.
‣ DenseDTableFSA( fsa ) | ( function ) |
fsa must be deterministic. The transition table is returned as a list of lists, where the e-th entry in the s-th inner list is TargetDFA (4.1-13), called as TargetDFA(fsa,e,s);.
‣ SparseTableFSA( fsa ) | ( function ) |
The transition table is returned as a list of lists, where each entry in the s-th inner list is is a two-element list [e,t] of integers that represents a transition from state number s to state number t under letter number e. We can also have e=0, representing transitions with no label (ϵ transitions).
‣ TargetDFA( fsa, e, s ) | ( function ) |
fsa must be a deterministic fsa, e should be a number or name of a letter of the alphabet, and s a number of a state of fsa. The target of s under e is returned, or 0 if there is no target.
‣ TargetsFSA( fsa, e, s ) | ( function ) |
Similar to TargetDFA (4.1-13), but fsa need not be deterministic, and a list of targets is returned.
‣ SourcesFSA( fsa, e, s ) | ( function ) |
Similar to TargetsFSA (4.1-14), but the list of sources of transitions to s under e is returned. Note that e can also be zero here.
‣ WordTargetDFA( fsa, w ) | ( function ) |
fsa must be a deterministic fsa, and w should be a list of integers or a word in the alphabet (in the case when the alphabet is defined from a free group or monoid). The target of the initial state of fsa under w is returned, or 0 if there is no such target.
‣ IsAcceptedWordDFA( fsa, w ) | ( function ) |
fsa must be a deterministic fsa, and w should be a list of integers or a word in the alphabet (in the case when the alphabet is defined from a free group or monoid). This function tests whether w is in the language of fsa.
‣ AddStateFSA( fsa ) | ( function ) |
Adds an extra non-accepting state to fsa with no transitions to or from it.
‣ DeleteStateFSA( fsa ) | ( function ) |
Deletes the highest numbered state together with all transitions to and from it from fsa. Use PermuteStatesFSA (4.1-20) first to delete a different state.
‣ PermuteStatesFSA( fsa, p ) | ( function ) |
p should be a permutation of [1..ns], where fsa has ns states. The states are permuted, where the original state number n becomes the new state number n^p.
‣ AddLetterFSA( fsa[, name] ) | ( function ) |
Adds an extra letter to the alphabet of fsa with no associated transitions. If the alphabet of fsa is defined over a free group or monoid, then name specifies the element of this free structure corresponding to the new letter.
‣ DeleteLetterFSA( fsa ) | ( function ) |
Deletes the highest numbered letter together with all associated transitions from the alphabet of fsa. Use PermuteLettersFSA (4.1-23) first to delete a different letter.
‣ PermuteLettersFSA( fsa, p ) | ( function ) |
p should be a permutation of [1..na], where the alphabet of fsa has na letters. The letters are permuted, where the original letter number n becomes the new letter number n^p.
‣ AddEdgeFSA( fsa, e, s, t ) | ( function ) |
Adds an extra transition to fsa with source s, target t and letter e. If there is already such a transition, then this function does nothing.
‣ DeleteEdgeFSA( fsa, e, s, t ) | ( function ) |
Deletes the transition from fsa with source s, target t and letter e, if there is one.
‣ SetAcceptingFSA( fsa, s, flag ) | ( function ) |
flag should be true or false, and state number s is made accepting or non-accepting, respectively.
‣ SetInitialFSA( fsa, s, flag ) | ( function ) |
flag should be true or false, and state number s is made initial or non-initial, respectively.
‣ IsAccessibleFSA( fsa ) | ( function ) |
Tests whether fsa is accessible; that is, whether all states can be reached from the initial states.
‣ AccessibleFSA( fsa ) | ( function ) |
Removes all inaccessible states from fsa thus rendering it accessible without altering its language.
‣ IsTrimFSA( fsa ) | ( function ) |
Tests whether fsa is trim; that is, whether all states can be reached from the initial states, and a final state can be reached from all states.
‣ TrimFSA( fsa ) | ( function ) |
Removes all inaccessible states from fsa and all states from which an accepting state cannot be reached, thus rendering it trim without altering its language.
‣ IsBFSFSA( fsa ) | ( function ) |
Tests whether fsa is in bfs (breadth-first-search) form; that is, whether the initial states come first and the other states appear in ascending order if one scans the transition table first by state number and then by alphabet number. Note that fsa must be accessible for it to be bfs.
‣ BFSFSA( fsa ) | ( function ) |
Replaces fsa by one with the same language but in bfs form. This can be useful for comparing the languages of two fsa. In fact MinimizeFSA (4.2-2) and BFSFSA are applied in turn to a deteministic fsa, then the resulting transition table is uniquely determined by the language of the fsa.
‣ LSizeDFA( fsa ) | ( function ) |
The size of the acceted language of fsa, which must be deterministic. This only works if fsa is trim. If not, then TrimFSA (4.1-31) must be called first.
‣ LEnumerateDFA( fsa, min, max ) | ( function ) |
The words in the language of fsa of length l satisfying min ≤ l ≤ max are returned in a list. The words will either be lists of integers, for simple type alphabets, of lists of words in the underlying free group or monoid for alphabets of type identifiers.
The remaining fsa functions all call external programs from the standalone. All of them except DeterminizeFSA (4.2-1) take only deterministic fsa as input, and all of them return deterministic fsa as output.
‣ DeterminizeFSA( fsa ) | ( function ) |
Returns a deterministic fsa with the same language as fsa.
‣ MinimizeFSA( fsa ) | ( function ) |
Returns a fsa with the same language as fsa and a minimal number of states.
‣ NotFSA( fsa ) | ( function ) |
Returns a fsa with the same alphabet as fsa whose language is the complement of that of fsa.
‣ StarFSA( fsa ) | ( function ) |
Returns a fsa whose language is L^*, where L is the language of fsa.
‣ ReverseFSA( fsa ) | ( function ) |
Returns a fsa whose language consists of the reversed words in the language of fsa.
‣ ExistsFSA( fsa ) | ( function ) |
fsa should be two-variable fsa on an alphabet A. An fsa is returned that accepts a word w_1 ∈ A^* if and only if there exists a word w_2 ∈ A^* with (w_1,w_2) in the language of fsa.
‣ SwapCoordsFSA( fsa ) | ( function ) |
fsa should be two-variable fsa on an alphabet A. A two-variable fsa on A is returned that accepts (w_1,w_2) if and only if (w_2,w_1) is accepted by fsa.
‣ AndFSA( fsa1, fsa2 ) | ( function ) |
fsa1 and fsa2 must have the same alphabet. The returned fsa has language equal to the intersection of those of fsa1 and fsa2.
‣ OrFSA( fsa1, fsa2 ) | ( function ) |
fsa1 and fsa2 must have the same alphabet. The returned fsa has language equal to the union of those of fsa1 and fsa2.
‣ ConcatFSA( fsa1, fsa2 ) | ( function ) |
fsa1 and fsa2 must have the same alphabet. The returned fsa accepts words of the form w_1w_2, where w_1 and w_2 are in the languages of fsa1 and fsa2, respectively.
‣ LanguagesEqualFSA( fsa1, fsa2 ) | ( function ) |
fsa1 and fsa2 must have the same alphabet. This function tests whether the languages of fsa1 and fsa2 are equal, and returns true or false.
‣ GrowthFSA( fsa ) | ( function ) |
Returns the growth function of fsa. This is a rational function, of which the the coefficient of x^n in its Taylor expansion is equal to the number of words of length n in the accepted language of fsa.
If the coefficients in this rational function are larger than about 16000 then strange error messages will appear and fail will be returned.
generated by GAPDoc2HTML