Subject: Re: [xsl] NFA to DFA conversion using XSLT From: "Mukul Gandhi" <gandhi.mukul@xxxxxxxxx> Date: Thu, 31 May 2007 23:46:26 +0530 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] NFA to DFA conversion usi, Michael Kay | Thread | Re: [xsl] NFA to DFA conversion usi, Dimitre Novatchev |
RE: [xsl] NFA to DFA conversion usi, Michael Kay | Date | Re: [xsl] NFA to DFA conversion usi, Dimitre Novatchev |
Month |