Return a list of all the non-accepting states in $fa.

Return the number of accepting or non-accepting states in $fa.

Return a new regular language object for prefixes of $lang. This means all strings S for which there exists some T where S.T is in $lang. For example if "abc" is in $lang then $new_lang has all prefixes "", "a", "ab", "abc".

The default is to allow T empty, so all strings of $lang are included in $new_lang. Optional parameter $proper true means T must be non-empty so only proper prefixes S are accepted.

In both cases prefix S can be the empty string, if suitable T exists. For $proper false this means if $lang accepts anything at all (! $lang->is_empty). For $proper true it means if $lang accepts some non-empty string.

Return a list of those states which prefix() would make accepting (and all other states non-accepting).

This is all ancestor states of the accepting states in $fa, so the predecessors of accepting, the predecessors of them, etc. The default $proper false includes the original accepting states (so all original strings of $fa). For $proper the original accepting states are not included, unless they occur as ancestors. (If they do, and are reachable from starting states, then it means there are already some prefixes accepted by $fa.)

No attention is paid to start states and what might be reached from them. This allows prefixing to be found or manipulated before setting starts.

$fa can be modified to accept also its prefixes like a non-copying form of $fa->prefix() by

$fa->set_accepting($fa->get_prefix_states);

get_prefix_accepting returns states which are not accepting but which by some sequence of symbols are able to reach accepting.

Some states of $fa may be non-accepting, but able to reach an accepting state by some sequence of symbols. get_prefix_accepting() returns a list of those states.

prefix_accepting() returns a new FLAT which has these "prefix accepting" states set as accepting. The effect is to accept all strings $fa does, and in addition accept all prefixes of strings accepted by $fa, including the empty string.

Prefix accepting states are the predecessors of accepting states, and predecessors of those prefix states, etc. This usually extends back to starting states, and includes those states. But no attention is paid to starting-ness, the process just continues back by predecessors, irrespective of what might be actually reachable from a starting state.

Some states of $fa may be "eventually accepting" in the sense that after more symbols they are certain to reach accepting, for all possible further symbol values.

For example suppose alphabet a,b,c. If bba, bbb and bbc are all accepted by $fa then string "bb" is reckoned as eventually accepted since one further symbol, any of a,b,c, goes to accepting.

get_eventually_accepting() returns a list of states which are eventually accepting. eventually_accepting() returns a clone of $fa which has those states set as accepting.

Eventually accepting states are found first as any state with all symbols going to accepting, then any state with all symbols going to either accepting or eventually accepting, and so on until no more such further states.

In an NFA, any epsilon transitions are crossed in the usual way, but there should be just one starting state (or just one which ever leads to accepting). If multiple starting states then the simple rule used will sometimes fail to find all eventually accepting states and hence strings. as_dfa will collapse multiple starts.

Return a FLAT::DFA which matches digits of fraction $num/$den. The DFA remains accepting as long as it is given successive digits of the fraction, and goes non-accepting (and remains so) on a wrong digit.

The default is decimal digits, or optional key/value

radix  => integer>=2

If $num/$den is an exact fraction in $radix, meaning $num/$den == n/$radix**k for some integer n,k, then it has two different representations. Firstly terminating digits followed by trailing 0s, secondly $n-1 followed by trailing $radix-1 digits.

For example 42/100 is 420000... and 419999... Both digit sequences converge to 42/100. For fractions not an exact power of $radix there is just one digit sequence which converges to $num/$den.

$num == 0 gives a DFA matching 000..., or $num==$den for fraction $num/$den == 1 gives a DFA matching 9999... (or whatever $radix-1).

In all cases the $fa->alphabet is all the digits 0 to $radix-1. Those which are "wrong" digits at a given point go to a non-accepting sink state. This is designed so that $fa->complement gives all digit strings except fraction $num/$den.

MAYBE: Option to omit wrong digits in an NFA, so transitions only for the accepted digits.

MAYBE: Currently the symbols for digits in a radix 11 or higher are decimal strings, but that might change. Could have an option for hex or a table or func. Decimal strings are easy to work with their values in Perl if a further func might act on the resulting FLAT. FLAT_rename can always change for final result if desired.

Return a copy of $fa which has separate sink states.

A sink state is where all out transitions loop back to itself. If two or more states go to the same sink then the return has new states so that each goes to its own such sink. The new sinks are the same accepting or not as each original sink.

This does not change the strings accepted, but can help viewing a big diagram where many long range transitions go to a single accepting and/or non-accepting sink.

Only single sink states are sought. Multiple states cycling among themselves all the same accepting or non-accepting are sinks, but they can be merged by an as_min_dfa.

Return true if $state has all transitions go to itself.

Add a state to $fa which is a copy of $state. Transitions out and accepting-ness of $new_state and the same as $state. Return the new state number.

$fa is a FLAT::NFA or FLAT::DFA accepting digit strings. Return a new FLAT (same DFA or NFA) which accepts numbers +1, or +/- a given increment. Key/value options are

add       => integer, default 1
radix     => integer>=2, default from alphabet
direction => "hightolow" (default) or "lowtohigh"

Option add => $add is the increment to apply (default 1). This can be negative too.

Option radix => $radix is the digit radix. The default is taken from the digits appearing in $fa->alphabet which is usually enough. The option can be used if $fa might not have all digits appearing in its alphabet.

Digit strings are taken as high to low. Option direction => "lowtohigh" takes them low to high instead. Low to high is more efficient here since manipulations are at the low end (add the increment and carry up through low digits), but both work.

An increment can increase string length, for example 999 -> 1000. If there are high 0s on a string then the carry propagates into them and does not change the length, so 00999 -> 01000.

Negative increments do not decrease string length, so 1000 -> 0999. If $add reduces a number below 0 then that string is quietly dropped.

If the strings matched by $fa represent a predicate, numbers with some property, then the returned $new_fa is those N for which N-add has the property. This is since $new_fa is +add from the originals. So to get a predicate testing whether N+1 has the property, apply an add => -1. An intersect() of that and the original becomes a predicate for a pair N and N+1 both with the property and longer runs can be made by further intersects.

ENHANCE-ME: Maybe a width option to stay in given number of digits, discard anything which would increment to bigger. Or a wraparound option to ignore carry above width for modulo radix^width.

ENHANCE-ME: Maybe decrement should trim a high 0 digit. That would mean a set of strings without high 0s remains so on decrement. But if say infinite high 0s are present then wouldn't want to remove them. Perhaps when a decrement goes to 0 it could be checked for an all-0s accepting state above, and merge with it.

This function works by modifying the digits matched in $fa, low to high. For example if the starting state has a transition for low digit 4 then the $new_fa has starting state with transition for digit 5 instead. At a given state there is a certain carry to propagate. At the starting states this is $add, and later it will be smaller. Existing states are reckoned as carry 0. A new state is introduced for combinations of state and non-zero carry reached. Transitions in those new states are based on the originals. Where the original state has digit d the new state has (d+carry) mod 10 and goes to the original successor and new_carry = floor((4+carry)/10). If that new_carry is zero then this is the original successor state since the increment is now fully applied. If new_carry is non-zero then it's another new state for combination of state and carry. In a FLAT::NFA any epsilon transitions are stepped across to find what digits in fact occur at the given state. In general an increment +1 propagates only up through digit 9s so that say 991 -> 002 (low to high). Often $fa might match only a few initial 9s and so only a few new states introduced.

ENHANCE-ME: Could have some generality by reckoning the carry as an arbitrary key or transform state, and go through $fa by a composition. Any such transformation can be made with a finite set of possible keys.

Return a new regular language object, of the same type as $lang, which matches the strings of $lang with 1 initial or final symbol skipped.

A string of 1 symbol in $lang becomes the empty string in $new_lang. The empty string in $lang cannot have 1 symbol skipped so is ignored when forming $new_lang.

In a FLAT::FA, skip_initial() works by changing the starting states to the immediate successors of the current starting states. For a FLAT::DFA, if this results in multiple starts then they are converted to a single start by the usual as_dfa(). skip_final() works by changing the accepting states to their immediate predecessors.

No minimization is performed. It's possible changed starts might leave some states unreachable. It's possible changed accepting could leave various states never reaching an accept.

ENHANCE-ME: maybe parameter $n to skip how many.