# NFA to DFA in joy

## icpdesign — 2005-09-11 19:49:19

    Does someone used Joy as a finite automata? How  Deterministic Finite Automton should be

    defined in Joy. Also, how do we implement the algorithm of converting a nondeterminisitic

    finite automata (NFA) to a determinisitic finite automata (DFA).

    I am learning Joy and looking for Joy programs implementing known algorithms, like  the one

    to covert an NFA to DFA

    Thanks

    Taoufik

## William Tanksley, Jr — 2005-09-11 21:59:24

    icpdesign <taoufik.dachraoui@...> wrote:

     > Does someone used Joy as a finite automata? How  Deterministic Finite Automton

    > should be

    > defined in Joy. Also, how do we implement the algorithm of converting a nondeterminisitic

    > finite automata (NFA) to a determinisitic finite automata (DFA).

     I've done DFAs in Forth, but never in Joy. I used a little toolkit

    someone else wrote that lets you build a jump table using a table-like

    syntax, so I was able to draw the state transition table directly in

    the source code.

    If you're wanting to convert an NFA to a DFA, you'll want a graph

    structure rather than a table structure. That should be pretty easy in

    Joy.

     > Taoufik

     -Billy

## phimvt@lurac.latrobe.edu.au — 2005-09-14 07:02:54

    On Sun, 11 Sep 2005, icpdesign wrote:

     > Does someone used Joy as a finite automata? How Deterministic Finite

    > Automton should be defined in Joy. Also, how do we implement the

    > algorithm of converting a nondeterminisitic finite automata (NFA) to a

    > determinisitic finite automata (DFA).

    >

    > I am learning Joy and looking for Joy programs implementing known algorithms, like  the one

    > to covert an NFA to DFA

     The conversion algorithm is just 4 lines of plain English in Aho

    and Ullman, Introduction to Automata Theory, Languages and Computation,

    p 22. I doubt whether anyone would want a conversion program, since

    just writing the NFA acceptor is exactly the same as writing a DFA

    acceptor in which the states are sets. So one might as well write

    the NFA table as DFA table.

    If you do not need more than 32 states in your NFA, (say 0..31),

    then you can use Joy sets (with the Boolean operations not, and or).

    Your input is a sequence, either a Joy list of characters or a string.

    You for each of the input symbols you need a function which returns,

    for the given input symbol and an arbitrary state, a set of possible

    new states. So one way of representing that is to have, for each

    input symbol, a list of sets, where the i-th set (i = 0..31) is the

    set of next states. This way at least the sets can be indexed.

    Alternatively, have just one big ordered list, of as many sublists as

    there are symbols, where each sublist is an ordered list of sets as

    above. This probably best.

    The accepting algorithm then is (writen in "pre-Joy", but not too "pre"):

    Let the accumulator of current states be {0}. (Start)

    Stepping through the input sequence (Use Joy "step") do this:

        use the current input symbol to index into the big list,

        start a new accumulator {},

        for each of the states in the old accumulator (again use "step"),

            index for that state into the set of next states

            and form the union (Joy "or") of that set of state

            with the new  accumulator.

    The end of the input sequence has been reached.

    Test whether the current accumulator (the last set of states) shares a

    member with the set of accepting states (test whether their "and"

    is non-empty). If so, ACCEPT, else REJECT the input sequence.

    The above is essentially a table driven acceptor - the acceptor

    interprets the table (the same as yacc and lex do). You could

    of course also have a Joy program which has the table built in,

    so to speak - the way handwritten parsers and scanners work.

    I'm not sure what you had in mind.

    Hope this helps.

      - Manfred