[augeas-devel] [libfa] Create a sub-dfa given a dfa and one of its states

[David Lutterkort]

Hi Filippo,

sorry for the very tardy reply. The struct fa keeps all states in a linked
list, and the first entry in the list is the initial state of the
automaton. If you just set fa->initial to some state along the list, I
think you'll end up leaking memory. In addition, you shouldn't change the
deterministic and minimal flags since whether the FA is deterministic
doesn't change with this operation; I am not entirely sure how taking a
subautomaton reflects on whether the FA is minimal or not. It might be
safest to just set fa->minmal to 0.

In terms of list manipulation, there's a helper `set_initial` that does
what you need it to. Overall, the code would look like this:

/* Turn fa into an FA with initial state st */
void fa_subfa(struct fa* fa, state *st) {
  set_initial(fa, st);
  fa->minimal = 0;
  collect(fa);
}

David

On Wed, Mar 25, 2020 at 6:42 AM Filippo Bistaffa <filippo.bistaffa at gmail.com>
wrote:

> Hi all,
> I hope this mail finds you all well during these times.
> I am using libfa in a project, and one of the tasks I am trying to
> achieve is: given a DFA and one of its states S, create a new "sub-DFA"
> starting from the state S.
>
> As an example, given this DFA and the state 0x56191c217e90:
>
> [image: 0.dot.png]
> i want to produce the sub-DFA
> [image: example.dot.png]
>
> My current (non-working) attempt is:
>
> struct fa *fa_subfa(struct state *st) {
>     struct fa *fa = fa_make_empty();
>     if (fa) {
>         fa->initial = st;
>         fa->deterministic= 1;
>         fa->minimal = 1;
>     }
>     return fa;
> }
>
> I am not getting the expected results because the internal state list is
> not correct.
> What is the best way to achieve this?
>
> Thanks in advance,
> Filippo Bistaffa
> _______________________________________________
> augeas-devel mailing list
> augeas-devel at redhat.com
> https://www.redhat.com/mailman/listinfo/augeas-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listman.redhat.com/archives/augeas-devel/attachments/20200830/e4d5b3e7/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0.dot.png
Type: image/png
Size: 134391 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/augeas-devel/attachments/20200830/e4d5b3e7/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example.dot.png
Type: image/png
Size: 78093 bytes
Desc: not available
URL: <http://listman.redhat.com/archives/augeas-devel/attachments/20200830/e4d5b3e7/attachment-0001.png>