NFA to DFA

Question

NFA can be converted into DFA using

• A. Sub set construction method
• B. Lazy evaluation method
• C. either A or B
• D. both A and B

Answer 1

Both are used to convert NFA to DFA.

There is a disadvantage with subset construction method , as we have to design a big transition table for the states with their input transition and which is very complex and takes a lot of time.

Its time complexity comes in 2ⁿ , which is exponential .

Hence we use lazy evaluation to avoid designing such big transition table .

hence, option C.

Answer 2

C. A OR B IS THE ANS

EVERYBODY KNOWS SUBSET CONSTRUCTION IS THE METHOD TO CONVERT FROM NFA TO DFA

AND LAZY EVALUATION JUST REFERS TO THE RENAMING OF STATES THAT WE GOT FROM SUBSET CONSTRUCTION.. THAT MEANS IT IS JUST A DELAY TO SIMPLIFY THE DIAGRAM

REFER HERE

https://quickgrid.wordpress.com/2015/10/30/converting-nfa-to-dfa-by-complete-and-lazy-subset-construction/

Comments

Can I convert NFA to DFA by using Lazy evaluation method ALONE?

---

READ THE ABSTRACT  FROM HERE

http://assaf.net.technion.ac.il/files/2013/01/DEBS-2015.pdf

---

YES .

THINK ON SCENIARIO: IN WHICH SO MANY EQUAL STATES AND FINAL STATES ARE THERE .IN THIS IF U SIMPLY PROCEED WITH SUBSET CONSTRUCTION THEN U WILL WASTE TIME ONLY..

SO INITIALY CHANGE THE EQUAL STATES =TO ONE STATE...(LAZY EVALUATION WORKS HERE)

Answer 3

Subset construction

Option A

Since Subset construction is method of converting NFA to DFA

Lazy evaluation is renaming states not converting 

Even without Renaming we can have NFA to DFA

Let me know if any thing wrong