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

  • Thread starter crazyautomata
  • Start date
  • Tags
    Equivalence
In summary, an NFA (non-deterministic finite automaton) allows for multiple possible transitions from a given state, while a DFA (deterministic finite automaton) only allows for a single transition. These have different language recognition capabilities, with NFAs being more flexible but DFAs being easier to implement and analyze. The equivalence of NFAs and DFAs means that they recognize the same language, and knowing this allows us to choose the most suitable automaton for a problem. This can be shown through the use of the subset construction algorithm, which converts an NFA into an equivalent DFA. However, there are some limitations to the equivalence, as there are some non-regular languages that cannot be recognized by a DFA.
  • #1
crazyautomata
3
0
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!
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
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.
 

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

1. What is the difference between an NFA and a DFA?

An NFA (non-deterministic finite automaton) is a type of finite automaton that allows for multiple possible transitions from a given state, while a DFA (deterministic finite automaton) only allows for a single transition. This makes NFAs more flexible in their language recognition capabilities, but DFAs are easier to implement and analyze.

2. What does it mean for an NFA to be equivalent to a DFA?

In the context of language recognition, two automata are considered equivalent if they recognize the same language. This means that they accept the same set of strings and reject the same set of strings.

3. Why is it useful to show the equivalence of NFAs and DFAs?

Proving that an NFA and a DFA are equivalent allows us to choose which type of automaton to use based on the specific requirements of a problem. NFAs are more expressive, but DFAs are more efficient in terms of both time and space complexity. Knowing that they are equivalent means we can use either one without affecting the final outcome.

4. How can we show that an NFA is equivalent to a DFA?

This can be done through the use of the subset construction algorithm, which converts an NFA into an equivalent DFA. The algorithm is based on the idea that the power set of an NFA's states can be mapped to the states of a DFA, with transitions between states based on the possible transitions in the NFA.

5. Are there any limitations to the equivalence of NFAs and DFAs?

Yes, there are some languages that cannot be recognized by a DFA, no matter how many states it has. These languages are known as non-regular languages. However, any regular language can be recognized by both a DFA and an NFA, and therefore, they are equivalent for all regular languages.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Programming and Computer Science
Replies
6
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
929
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
692
  • Introductory Physics Homework Help
3
Replies
97
Views
14K
  • Special and General Relativity
Replies
17
Views
2K
Replies
13
Views
2K
Back
Top