Question: Converting NFA to DFA: Checking for Errors and Improving Technique

  • MHB
  • Thread starter Lolligirl
  • Start date
  • Tags
    Dfa
In summary, Evgeny suggests that the states of the new DFA be subsets of states of the NFA. He also suggests using the procedure in the constructive proof that NFAs are reducible to DFAs. He provides a DFA that is equivalent to the NFA and also allows loops back.
  • #1
Lolligirl
23
0
Hello again everyone! I think I have at least a decent handle on this one, but I want to check my work.

Question: Convert the following NFA to an equivalent DFA (The D is going to B and the E to A on lambda).
https://dl.dropboxusercontent.com/u/5778771/Assignment4GivenNFA.jpg

Here is my DFA so far:
https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1.png

Are there any errors that pop out at any of you?

Thanks! :D
 
Technology news on Phys.org
  • #2
Lolligirl said:
Hello again everyone! I think I have at least a decent handle on this one, but I want to check my work.

Question: Convert the following NFA to an equivalent DFA (The D is going to B and the E to A on lambda).Here is my DFA so far:Are there any errors that pop out at any of you?

Thanks! :D

Hi Lolligirl!

Well, your DFA will only accept words that the NFA also accepts, so that is good. :)
Oh, and you will need a start state. :eek:

However, the NFA allows loops back, but your DFA doesn't.
So the NFA would accept for instance [m]aaaa[/m], but your DFA doesn't.
 
  • #3
That...is a good point. Could I perhaps do this?

https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1v2.png

...But, looking at it, now there's an extra character at the end before it wraps back around to 0. I could perhaps delete my state 4 altogether and simply make state 3 wrap around on an 'a' to state 0 which would then be an accept state...but then the DFA would accept strings the NFA doesn't. Could you give me a push in the right direction of where my mistake in logic is?
 
Last edited:
  • #4
I suggest using the procedure in the constructive proof that NFAs are reducible to DFAs. That's where the states of the new DFA are subsets of states of the NFA. In my attempt, the DFA ends up having only 5 states instead of the possible maximum of $2^5=32$.
 
  • #5
Okay, maybe you can help me clear something up here. My confusion starts at the bolded line (here I am relabeling the A, B, etc. letters for the original states as numbers to distinguish this DFA from the NFA on my paper; E(blah) is the epsilon closure of blah).

For convenience, here's the NFA again:
https://dl.dropboxusercontent.com/u/5778771/Assignment4GivenNFA.jpg

E(0) = {0} = A (renaming {0} to A)
E(move(A,a)) = E({1}) = {1} = B
E(move(A,b)) = E({Ø}) = {Ø} = Ø

E(B) aka E({1})
E(move(B,a)) = E({2,4}) = {0,2,4} = C
E(move(B,b)) = E({Ø}) = {Ø} = Ø

At this point, we have:
https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1v3.jpg

Now, continuing:
E(C) aka E({0,2,4})
E(move(C,a)) = E({1})
OR
E(move(C,a)) = E({0,1,2,4})

^Which one of the two is it? Move(C,a) itself would be just {1} if I'm thinking of this correctly, but the epsilon closure of that is {1}...it feels like I'm leaving out the {0,2,4}. Hopefully you understand what I mean.

If I go along with E(move(C,a)) = E({1}), finish E(move(C,b)), as well as finish state D's outgoing arrows, this is the resulting DFA I get, but I'm not sure if it's correct:
https://dl.dropboxusercontent.com/u/5778771/Assignment4Number1v4.jpg
 
Last edited:
  • #6
Lolligirl said:
here I am relabeling the A, B, etc. letters for the original states as numbers to distinguish this DFA from the NFA on my paper
I think it would be clearer to keep $A,B,\dots$ to be the state names of the old NFA and introduce new names like $P,Q,\dots$ or $1,2,\dots$ for the states of the new DFA.

Lolligirl said:
Now, continuing:
E(C) aka E({0,2,4})
E(move(C,a)) = E({1})
OR
E(move(C,a)) = E({0,1,2,4})

^Which one of the two is it?
The first variant is correct. The transition function $\operatorname{move}'$ of the DFA is defined as
\[
\operatorname{move}'(R,a)=E\left(\bigcup_{r\in R}\operatorname{move}(r,a)\right).
\]
Here $r$ is one of the old states and $R$ is a subset of the old states. For this automaton, $\bigcup_{r\in\{0,2,4\}}\operatorname{move}(r,a)=\{1\}$ and $E(\{1\})=\{1\}=B$.

Lolligirl said:
Move(C,a) itself would be just {1} if I'm thinking of this correctly, but the epsilon closure of that is {1}
That is correct. Your resulting DFA is also correct.
 
  • #7
...Oh! So that's what that notation means! I keep seeing that notation with unions and belongs to and primes everywhere, but I never really saw it used next to a picture, so I didn't understand what it was trying to say. Thank you so much for clearing that up, Evgeny; now I see how my thinking was right, and how to improve my technique further (as well as improve my notation)! :D
 
Last edited:

Related to Question: Converting NFA to DFA: Checking for Errors and Improving Technique

1. What is an NFA and a DFA?

An NFA (Nondeterministic Finite Automaton) and a DFA (Deterministic Finite Automaton) are two types of finite state machines used in automata theory and computer science. They are mathematical models that can recognize patterns in strings of characters and are used in programming languages, compilers, and other applications.

2. Why do we need to convert an NFA to a DFA?

Converting an NFA to a DFA can simplify the automaton and make it easier to analyze and understand. DFAs are also generally faster and more efficient in recognizing patterns compared to NFAs.

3. How do we convert an NFA to a DFA?

The process of converting an NFA to a DFA involves creating a new DFA with the same language as the NFA. This is done by creating a state in the DFA for every possible combination of states in the NFA, and then determining the transitions and accepting states based on the transitions in the NFA.

4. What are the advantages and disadvantages of converting an NFA to a DFA?

The advantages of converting an NFA to a DFA include a simplified and more efficient automaton, as well as the ability to use existing algorithms and tools designed for DFAs. However, the conversion process can be time-consuming and may result in a larger automaton compared to the original NFA.

5. Are there any limitations to converting an NFA to a DFA?

Yes, there are some languages that cannot be recognized by a DFA and require an NFA. These languages include those with patterns that require backtracking or multiple paths to be recognized. In these cases, converting an NFA to a DFA may not be possible.

Similar threads

  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
6
Views
3K
  • Programming and Computer Science
Replies
6
Views
12K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
6
Views
2K
  • Topology and Analysis
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Programming and Computer Science
Replies
29
Views
3K
Replies
16
Views
3K
Replies
1
Views
1K
Back
Top