On Mar 21, 8:11 am, "andrew cooke" <and...@acooke.org> wrote:
> J-Burns wrote:
snip
> > For example, this means that there can be a start node supposedly.
> > Having a value of 0. It is pointing to node 1 with the value of "a"
> > and to node 2 with the value of "b". Trying to make something like an
> > NFA. Where id be changing regular expressions to NFAs.
>
> > How can I do this? And if I could do this by some other way than using
> > linked lists than do tell me about that as well.
>
> when you mention NFAs and regular expressions, you make me think that you
> don't want a linked list at all, but a graph. there are various ways of
> storing a graph, but one of the simplest is to use a dict() that maps from
> source to destination node(s).
>
> in your case you could use ints for the nodes and a dict([int]) for the
> graph. so:
>
> {1: [2,3], 2: [3], 3: [3]}
>
> is a graph in which 1 and 2 are connected in each direction, both 1 and 2
> are linked to 3, and 3 has a loop that links back to itself.
>
> andrew
WARNING, spoiler.
So far, Andrew's and John's structures can be used for both a DFA and
a NFA. The only thing further you need is a collection instead of a
single value to hold current state.
states= set( [ 1 ] )
while 1:
_newstates= set( )
for state in states:
_newstates.update( transitions[ state ] )
states= _newstates
# or states.clear( ); states.update( _newstates )
How will you mark a state as 'final'/ success?
--
http://mail.python.org/mailman/listinfo/python-list
