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..
On 5/31/07, Michael Kay <mike(_at_)saxonica(_dot_)com> wrote:
> 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
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--