Results 1 to 1 of 1

Thread: Help on NFA's with plugin DFA's

  1. #1
    Dec 2011

    Help on NFA's with plugin DFA's

    Hello guys!
    I have been thinking about this problem for weeks and I'm still not sure if the problem is decidable or not. Basically it asks there are NFA's with states that can be substituted to DFA's. Given two such NFA's, determine whether they are equivalent in any possible DFA substitutions. Of course these two NFA's have states that are labelled with letters from a same variable set, and same variables will be substituted into same DFA's.

    Below is an example of such substitutions.

    Note the equivalence must hold with any possible plugins. For example, NFA A1 and A2 both has same variables X and Y, A1 and A2 are equivalent iff L(A1) = L(A2) for any two DFA's plugged into A1 and A2. Of course same DFA will be plugged into same variable in both NFA's.

    I have tried to prove the problem is decidable. However, I run into the trouble that although I can easily show two NFA's are equivalence before plugin the DFA's, this equivalence is only related to the strings they generate, not the sequences of states. It is still possible same variable symbol holds different states (by different, I mean different place along the sequence of states) in these two NFA's therefore the they generated different strings after plugging in DFA's.

    On the other hand, if this problem is undecidable, I can't find a reduction from any undecidable problems.

    Any thoughts on this problem will be really appreciated!

    Thank you!
    Attached Thumbnails Attached Thumbnails Help on NFA's with plugin DFA's-fah_4.jpg   Help on NFA's with plugin DFA's-fah_3.jpg   Help on NFA's with plugin DFA's-fah_2.jpg   Help on NFA's with plugin DFA's-fah_1.jpg  
    Last edited by mr fantastic; Dec 30th 2011 at 04:37 PM. Reason: Title.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Free Plugin?
    Posted in the LaTeX Help Forum
    Replies: 8
    Last Post: Sep 14th 2010, 11:01 AM

Search Tags

/mathhelpforum @mathhelpforum