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