The KBMag package contains GAP interfaces to many of the functions for manipulating finite state automata (\({\sf 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.
\({\sf 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 \({\sf fsa}\) will be used for both singular and the plural.)
The alphabet of an \({\sf 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 \({\sf 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 \({\sf fsa}\). The other possibilities for the user to construct a \({\sf 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 \({\sf fsa}\) is a record describing a valid initialized \({\sf fsa}\).
‣ InitializeFSA( fsa ) | ( function ) |
Initializes a record representing a \({\sf fsa}\) that has been read in from a file.
‣ FSA( alph ) | ( function ) |
Returns an initialized \({\sf 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 \({\sf fsa}\).
‣ WriteFSA( fsa ) | ( function ) |
Displays \({\sf fsa}\) nicely. (In a proper implementation, this would be the ViewObj function.)
‣ IsDeterministicFSA( fsa ) | ( function ) |
Tests whether \({\sf fsa}\) is a deterministic \({\sf fsa}\). Many of the functions below work only for deterministic \({\sf fsa}\). A deterministic \({\sf fsa}\) with the same language as \({\sf 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 \({\sf fsa}\).
‣ NumberOfStatesFSA( fsa ) | ( function ) |
Returns the number of states of \({\sf fsa}\).
‣ NumberOfLettersFSA( fsa ) | ( function ) |
‣ SizeOfAlphabetFSA( fsa ) | ( function ) |
Returns the size of the alphabet of \({\sf fsa}\).
‣ AcceptingStatesFSA( fsa ) | ( function ) |
Returns the list of accepting states of \({\sf fsa}\).
‣ InitialStatesFSA( fsa ) | ( function ) |
Returns the list of initial states of \({\sf fsa}\).
‣ DenseDTableFSA( fsa ) | ( function ) |
\({\sf 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 (\(\epsilon\) transitions).
‣ TargetDFA( fsa, e, s ) | ( function ) |
\({\sf fsa}\) must be a deterministic \({\sf fsa}\), \(e\) should be a number or name of a letter of the alphabet, and \(s\) a number of a state of \({\sf 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 \({\sf 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 ) |
\({\sf fsa}\) must be a deterministic \({\sf 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 \({\sf fsa}\) under \(w\) is returned, or \(0\) if there is no such target.
‣ IsAcceptedWordDFA( fsa, w ) | ( function ) |
\({\sf fsa}\) must be a deterministic \({\sf 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 \({\sf fsa}\).
‣ AddStateFSA( fsa ) | ( function ) |
Adds an extra non-accepting state to \({\sf 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 \({\sf 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 \({\sf 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 \({\sf fsa}\) with no associated transitions. If the alphabet of \({\sf 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 \({\sf 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 \({\sf 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 \({\sf 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 \({\sf 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 \({\sf fsa}\) is accessible; that is, whether all states can be reached from the initial states.
‣ AccessibleFSA( fsa ) | ( function ) |
Removes all inaccessible states from \({\sf fsa}\) thus rendering it accessible without altering its language.
‣ IsTrimFSA( fsa ) | ( function ) |
Tests whether \({\sf 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 \({\sf 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 \({\sf 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 \({\sf fsa}\) must be accessible for it to be bfs.
‣ BFSFSA( fsa ) | ( function ) |
Replaces \({\sf fsa}\) by one with the same language but in bfs form. This can be useful for comparing the languages of two \({\sf fsa}\). In fact MinimizeFSA (4.2-2) and BFSFSA are applied in turn to a deteministic \({\sf fsa}\), then the resulting transition table is uniquely determined by the language of the \({\sf fsa}\).
‣ LSizeDFA( fsa ) | ( function ) |
The size of the acceted language of \({\sf fsa}\), which must be deterministic. This only works if \({\sf 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 \({\sf fsa}\) of length \(l\) satisfying \(min \le l \le 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 \({\sf fsa}\) functions all call external programs from the standalone. All of them except DeterminizeFSA (4.2-1) take only deterministic \({\sf fsa}\) as input, and all of them return deterministic \({\sf fsa}\) as output.
‣ DeterminizeFSA( fsa ) | ( function ) |
Returns a deterministic \({\sf fsa}\) with the same language as \({\sf fsa}\).
‣ MinimizeFSA( fsa ) | ( function ) |
Returns a \({\sf fsa}\) with the same language as \({\sf fsa}\) and a minimal number of states.
‣ NotFSA( fsa ) | ( function ) |
Returns a \({\sf fsa}\) with the same alphabet as \({\sf fsa}\) whose language is the complement of that of \({\sf fsa}\).
‣ StarFSA( fsa ) | ( function ) |
Returns a \({\sf fsa}\) whose language is \(L^{*}\), where \(L\) is the language of \({\sf fsa}\).
‣ ReverseFSA( fsa ) | ( function ) |
Returns a \({\sf fsa}\) whose language consists of the reversed words in the language of \({\sf fsa}\).
‣ ExistsFSA( fsa ) | ( function ) |
\({\sf fsa}\) should be two-variable \({\sf fsa}\) on an alphabet \(A\). An \({\sf fsa}\) is returned that accepts a word \(w_1 \in A^{*}\) if and only if there exists a word \(w_2 \in A^{*}\) with \((w_1,w_2)\) in the language of \({\sf fsa}\).
‣ SwapCoordsFSA( fsa ) | ( function ) |
\({\sf fsa}\) should be two-variable \({\sf fsa}\) on an alphabet \(A\). A two-variable \({\sf fsa}\) on \(A\) is returned that accepts \((w_1,w_2)\) if and only if \((w_2,w_1)\) is accepted by \({\sf fsa}\).
‣ AndFSA( fsa1, fsa2 ) | ( function ) |
\({\sf fsa1}\) and \({\sf fsa2}\) must have the same alphabet. The returned \({\sf fsa}\) has language equal to the intersection of those of \({\sf fsa1}\) and \({\sf fsa2}\).
‣ OrFSA( fsa1, fsa2 ) | ( function ) |
\({\sf fsa1}\) and \({\sf fsa2}\) must have the same alphabet. The returned \({\sf fsa}\) has language equal to the union of those of \({\sf fsa1}\) and \({\sf fsa2}\).
‣ ConcatFSA( fsa1, fsa2 ) | ( function ) |
\({\sf fsa1}\) and \({\sf fsa2}\) must have the same alphabet. The returned \({\sf fsa}\) accepts words of the form \(w_1w_2\), where \(w_1\) and \(w_2\) are in the languages of \({\sf fsa1}\) and \({\sf fsa2}\), respectively.
‣ LanguagesEqualFSA( fsa1, fsa2 ) | ( function ) |
\({\sf fsa1}\) and \({\sf fsa2}\) must have the same alphabet. This function tests whether the languages of \({\sf fsa1}\) and \({\sf fsa2}\) are equal, and returns true or false.
‣ GrowthFSA( fsa ) | ( function ) |
Returns the growth function of \({\sf 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 \({\sf 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