Re: NFA to DFA conversion using XSLT

Hi Mike,
  Thanks for your reply.

I am toying with the following idea (a sample state table) to
represent state table of NFA:

<nfastates>
 <state name="0">
   <input symbol="a">
     <movetostate name="0" />
     <movetostate name="1" />
   </input>
   <input symbol="b">
     <movetostate name="0" />
   </input>
 </state>
 <state name="1">
   <input symbol="a">
     <movetostate name="none" />
   </input>
   <input symbol="b">
     <movetostate name="2" />
   </input>
 </state>
 <state name="2">
   <input symbol="a">
     <movetostate name="none" />
   </input>
   <input symbol="b">
     <movetostate name="3" />
   </input>
 </state>
 <state name="3" isfinal="yes" />
</nfastates>

(this is the NFA recognizing the language (a | b)*abb ). I am
following some examples and algorithms from the book, "Principles of
compiler design - by Aho, Ullman).

One of the algorithms for NFA to DFA conversion states, that we
essentially follow the below two steps:
1) Compute e-CLOSURE (e stands for epsilon transitions) - which
involves pushing & popping states from a stack.
2) The subset construction - which uses e-CLOSURE function to construct a DFA.

The book also describes an algorithm to minimize the number of states
of a DFA (whose output is a DFA accepting the same language as
original DFA, but having as few states as possible).

Do you think, we could do this with XSLT? As I defined the NFA above,
I can specify the meaning of a DFA similarly.

I recently read on Dimitre's blog, that he has written a framework for
LR-Parsing using XSLT 2.0. My interest is along the same lines..

> I am looking for a suitable W3C Schema to represent state
> table of a NFA.

I think there are such things in the context of workflow modelling (e.g.
BPEL) but it might carry a lot more baggage than you actually want.
>
> My second question is: is it easily possible to write a XSLT
> program (I can prefer 2.0 language if you wish) to convert a
> NFA to an equivalent (DFA, with minimal states).
>
Possible yes. Easy, I doubt it. I found it challenging enough in Java. But I
expect someone will prove me wrong!

Michael Kay
http://www.saxonica.com/

--
Regards,
Mukul Gandhi