| Subject: | NFA/DFA is_finite() |
| Date: | Wed, 06 Jul 2016 18:29:56 +1000 |
| To: | bug-FLAT [...] rt.cpan.org |
| From: | Kevin Ryde <user42_kevin [...] yahoo.com.au> |
In FLAT 0.9.1 on a debian i386 perl 5.22.1, a program
use strict;
use FLAT;
my $f = FLAT::Regex->new('a* b');
print "Regex ", $f->is_finite ? "finite\n" : "infinite\n";
$f = $f->as_nfa;
print "NFA ", $f->is_finite ? "finite\n" : "infinite\n";
prints Regex infinite but NFA finite. I expected NFA infinite too.
Nosing around the code, does the NFA only find cycles which include
accepting states? Maybe it would notice also cycles which precede an
accepting.
I suppose cycles around an accepting state would mean infinitely many
strings which have a prefix of themself also accepted. Or infinitely
many continuations of some other accepted strings. Is there usual
jargon for a flavour of infiniteness like that?
(I struck this when experimenting to subtract out strings containing an
accepted substring.)