1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: HELP: Equivalence of NFA's with plugin DFA's

  1. Dec 29, 2011 #1
    URGENT HELP: Equivalence of NFA's with plugin DFA's

    1. The problem statement, all variables and given/known data
    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.
    http://www.mathhelpforum.com/math-help/attachments/f37/23152d1325120151-urgent-help-nfas-plugin-dfas-fah_3.jpg [Broken]

    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.

    2. Relevant equations

    3. The attempt at a solution
    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 thought on this problem will be really appreciated!

    Thank you!
    Last edited by a moderator: May 5, 2017
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted