Automata, Languages and Compilers 2017/18 spring

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.

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) {
        ... f.apply(x) ... 
    }

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

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

Sellega arvutame sisuliselt järgmisi väärtusi:

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

        Set<Trans> rel1 = compose(rel0, rel0); System.out.println(rel1);
        Set<Trans> rel2 = compose(rel1, rel0); System.out.println(rel2);
        Set<Trans> 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 programmeerisime selle transitiivse sulundi, siis me kogusime compose tulemused kõik kokku ehk pigem oleks vaja arvutada fixpoint(x -> union(x, compose(x, rel)), rel). See töötab, aga õpikus kasutavad seda tüüpi funktsioonide distributiivsust ja hoitakse alles ainult esialgset hulka: fixpoint(x -> union(rel, compose(x, rel)), rel).

Defineeri nüüd funktsioon closure, mis võtab lisaks funktsioonile f ka argmendiks see esialgne hulk M ja arvutab funktsiooni {$ g(x) = M \cup f(x) $} püsipunkt, alustades arvutusi hulgast M:

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

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

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

Ja analoogiliselt muidugi epsilon-sulundiga...