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

[crazyautomata]

URGENT HELP: Equivalence of NFA's with plugin DFA's

Homework Statement

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

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.

Homework Equations

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!

 

[LightHero]

My Attempt:The problem is decidable. First of all, given two NFAs A1 and A2, we need to check if they are equivalent in any possible DFA substitutions. To do this, we can use a simple algorithm. First, we create an empty graph G. Then, for each state in both A1 and A2, we add a node to the graph G. For each transition of A1 and A2, we add an edge from the starting node to the ending node with the appropriate label. Finally, for each DFA D plugged into A1 and A2, we add a path in G from the start node to all the end nodes of the DFA D. Now, we can use a standard graph search algorithm to find out if the two NFAs are equivalent in any DFA substitution. Specifically, we can use a breadth-first search (BFS) to traverse the graph G, starting from the start node of A1 and A2. If we encounter the same end node after traversing the same path in both A1 and A2, then we can conclude that the two NFAs are equivalent in any DFA substitution. Otherwise, the two NFAs are not equivalent in any DFA substitution. Hence, the problem is decidable.