Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

RGPV TOC Short note on equivalent of DFA and NFA

Photo of author

By Team EasyExamNotes

RGPV 2010, 02
Q. Write short note on equivalent of DFA and NDFA ?

Ans. 
  1. Every DFA is an NDFA.
  2. If from a regular set an NDFA is created than there may be chances of existence of DFA.
DFA is 5 tuple machine:
M = (Q, Σ, δ, q0, F)
  1. Q is a finite non empty set of states.
  2. Σ is a finite non empty set of input symbols.
  3. δ is a transition function, QXΣ int to Q
  4. q0 is an initial state belong to Q.
  5. F is the set of final states belong to Q.
NDFA is 5 tuple machine:
M = ( Q, Σ, δ, q0, F )
  1. Q is a finite non empty set of states.
  2. Σ is a finite non empty set of input symbols.
  3. δ is a transition function, QXΣ int to 2Q 
  4. q0 is an initial state belong to Q.
  5. F is the set of final states belong to Q.
Problem 01: Convert the following Non-Deterministic Finite Automata (NDFA) to Deterministic Finite Automata (DFA).

Transition table for NDFA from above NDFA transition diagram

State

Input 0

Input 1

->q0

q0

q0, q1

q1

–

*q2

q2

–

–

Transition table for DFA from above NDFA transition table

State

Input a

Input b

->q0

q0

{q0, q1}

{q0, q1}

q0

*{q0, q1, q2}

*{q0, q1, q2}

q0

*{q0, q1, q2}

Transition diagram from above DFA transition table


Reference:

  1. Introduction to Automata Theory Language & Computation, Hopcroft& Ullman,
  2. Theory of Computation, Chandrasekhar & Mishra, PHI.

Download as PDF

Related posts:

  1. RGPV TOC What do you understand by DFA how to represent it
  2. RGPV Define Mealy and Moore Machine
  3. RGPV notes Write short note on NDFA
  4. NDFA accepting two consecutive a’s or two consecutive b’s.
  5. RGPV short note on automata
  6. RGPV TOC properties of transition functions
  7. RGPV TOC What is Trap state
  8. DFA which accept 00 and 11 at the end of a string
  9. CFL are not closed under intersection
  10. NFA to DFA | RGPV TOC
  11. Moore to Mealy | RGPV TOC PYQ
  12. DFA accept even 0 and even 1 |RGPV TOC PYQ
  13. Short note on automata | RGPV TOC PYQ
  14. DFA ending with 00 start with 0 no epsilon | RGPV TOC PYQ
  15. DFA ending with 101 | RGPV TOC PYQ
  16. Construct DFA for a power n, n>=0 || RGPV TOC
  17. Construct FA divisible by 3 | RGPV TOC PYQ
  18. Construct DFA equivalent to NFA | RGPV TOC PYQ
  19. CNF from S–>aAD;A->aB/bAB;B->b,D->d.
  20. Regular expresion to CFG
  21. Regular expression to Regular grammar
  22. Grammar is ambiguous. S → aSbS|bSaS|∈
  23. leftmost and rightmost derivations
  24. Construct Moore machine for Mealy machine
  25. Definition of Deterministic Finite Automata
  26. Notations for DFA
  27. How do a DFA Process Strings?
  28. DFA solved examples
  29. Definition Non Deterministic Finite Automata
  30. Moore machine
  31. Mealy Machine
  32. Regular Expression Examples
  33. Regular expression
  34. Arden’s Law
  35. NFA with ∈-Moves
  36. NFA with ∈ to DFA Indirect Method
  37. Define Mealy and Moore Machine
  38. What is Trap state ?
  39. Equivalent of DFA and NFA
  40. Properties of transition functions
  41. Mealy to Moore Machine
  42. Moore to Mealy machine
  43. Diiference between Mealy and Moore machine
  44. Pushdown Automata
  45. Remove ∈ transitions from NFA
  46. TOC 1
  47. Diiference between Mealy and Moore machine
  48. What is Regular Expression
  49. What is Regular Set in TOC
  50. DFA end with 1 contain 00 | RGPV TOC draw
  51. RGPV TOC design finite automata problems
  52. Minimization of DFA
  53. Construct NFA without ∈
  54. RGPV TOC PYQs
  55. Introduction to Automata Theory