Automaadid, keeled ja translaatorid

Püsipunkt ja sulund

NB! See osa ei ole kodutöö lahendamiseks vajalik. See ei ole ka kursuse läbimiseks vajalik. Seda tasub ainult lugeda, kui Sind huvitab, et lahendus oleks võimalikult lihtne, üldine ja elegantne.

Teemat tutvustav video: Sulund ja püsipunkt (slaidid).

Plaan on siin üritada õpiku põhjal implementeerida epsilon-sulundi arvutamist. Selle kohta on õpikus kirjas peatükis 1.5.1 ja selle taga olev matemaatika on selgitud Lisas A.4. See oli aga kodutöö ülesanne, mistõttu lahendame hoopis transitiivse sulundi ülesanne. Selleks aga ehitame väga üldise ja võimsa tööriista. Kuna saame selle abil arvutada suvalist sulundit, siis saame siin rahuliku südametunnistusega kodutöö ära lahendada... ;)

Püsipunkti leidmine

Alustame siin sellega, et meil on (monotoonne) funktsioon f ja tahame leida tema püsipunkt, s.t. selline x, et f(x)=x. Seda saab siis teha tema korduvalt rakendamise teel. Siin kasutame Java geneerilise meetodi ja funktsiooni liidest, et see töötaks iga funktsiooni f: T → T korral:

    public static <T> T fixpoint(UnaryOperator<T> f, T x) {
        while (true) {
            T next = f.apply(x);
            if (x.equals(next)) return x;
            x = next;
        }
    }

Transitiivne sulund???

Kui on vaja arvutada transitiivset sulundit, siis võiksime funktsiooni compose abil komponeerida relatsiooni endaga:

    public static Set<Transition> transitiveClosure(Set<Transition> rel) {
        return fixpoint(x -> compose(x, rel), rel);
    }

Sellega arvutame sisuliselt järgmisi väärtusi:

        Set<Transition> rel0 = new HashSet<>();
        rel0.add(new Transition(0, "a", 1));
        rel0.add(new Transition(1, "b", 2));
        rel0.add(new Transition(1, "c", 3));
        rel0.add(new Transition(3, "d", 4));

        Set<Transition> rel1 = compose(rel0, rel0); System.out.println(rel1);
        Set<Transition> rel2 = compose(rel1, rel0); System.out.println(rel2);
        Set<Transition> rel3 = compose(rel2, rel0); System.out.println(rel3);

See ei ole päris see, mida tahaks... kas oskad ennustada, mis siin valesti läheb?

Sulundi arvutamine

Kui ise programmeerimiksime selle sulundi, siis me koguks ju compose tulemused kõik kokku. Üldisemalt võib siis defineerida sellise meetodi, mis lahendab õpiku hulgavõrrandid alustades iteratsiooni tühjast hulgast:

    public static <T> Set<T> leastFixpoint(UnaryOperator<Set<T>> f) {
        return fixpoint(f, emptySet());
    }

Defineeri nüüd funktsioon closure, mis võtab lisaks funktsioonile f ka argumendiks see esialgne hulk M ja arvutab funktsiooni {$ g(x) = M \cup f(x) $} vähimat püsipunkti:

    public static <T> Set<T> closure(UnaryOperator<Set<T>> f, Set<T> m) {
        return leastFixpoint(x -> ???);
    }

Kui see on õigesti tehtud, siis saab transitiivse sulundi defineerida ühe reaga:

    public static Set<Transition> transitiveClosure(Set<Transition> rel) {
        return closure(x -> compose(x, rel), rel);
    }

Ja analoogiliselt muidugi epsilon-sulundiga...