| Subject: | suggest prefix of lang |
| Date: | Tue, 21 Mar 2017 18:07:25 +1100 |
| To: | bug-FLAT [...] rt.cpan.org |
| From: | Kevin Ryde <user42_kevin [...] yahoo.com.au> |
As an idea for a feature, it could be good to have something for getting
the "prefix" of an lang, accepting strings which are prefixes of strings
in FA.
I struck this when fiddling with bit strings representing fractions
written in binary. If a certain bit string is acceptable, up to that
many digits so far, then its prefixes are to be acceptable too.
I had a go at some code, finding all predecessors of accepting states,
or for Regex some slightly subtle mangling. I wrote some docs of what I
thought below. Does this sound likely?
There'd be more or different possible. Maybe a generic ancestors()
could find prefix states. An equivalent descendants() on starting
states would be what prune() retains. Maybe even queries about
prefix-ness, like whether a lang contains any prefix, all prefixes, or
is prefix-free (or what jargon). I had one place wanting to verify I
accepted all prefixes, but test ->equals(->prefix), or prefix states ==
accepting states, would be enough for now. Of course all of the above
could be similar for suffix too.
=item C<$new_lang = $lang-E<gt>prefix>
=item C<$new_lang = $lang-E<gt>prefix ($proper)>
Return a new regular language object for prefixes of C<$lang>. This means
all strings S for which there exists some T with S.T in C<$lang>.
If optional parameter C<$proper> is true, then T must be non-empty so that
only proper prefixes S are accepted. The default or C<$proper> false is to
accept the full strings of C<$lang> too.
In both cases S can be the empty string provided suitable T exists. For
C<$proper> false this means if C<$lang> accepts anything at all (C<!
$lang-E<gt>is_empty>). For C<$proper> true it means if C<$lang> accepts
some non-empty string.