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

RGPV notes Write short note on NDFA

Photo of author

By Team EasyExamNotes

RGPV 2002
Q. Write a short note on non-deterministic finite automta ?

Ans. Non deterministic finite automata refere as NDFA or NFA allows a set of possible moves. 
For example from a state an input ‘1’ can transit 0 times, 1 times or more than 1 times.
Its not determined in NFA like in DFA.
NDFA is defined as 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.
To understood NDFA, lets compare it with DFA.

NDFA

DFA

Non Deterministic Finite Automata

Deterministic Finite Automata

Empty String transition allowed in DDFA.

Empty String transition not allowed in DFA.

In NDDFA, the next possible state is not determined.

In DFA, the next possible state is determined.

For NDFA, DFA may or may not exist.

For all DFA there exist NDFA

NDFA is like combination of many machines.

DFA is like a single machine.

NDFA is easy to construct.

DFA is touch to construct compare to NDFA.

Some examples of NDFA:
Problem 01: Construct a NDFA for the language accepting strings having even number of 1’s over input alphabets ∑ = {0, 1}.

Problem 02: Construct a NDFA for the language accepting strings containg ’01’ as substring over input alphabets ∑ = {0, 1}.


Problem 03: Construct a NDFA for the language accepting strings containg ‘0’ as divisible by 3 over input alphabets ∑ = {0, 1}.
Download as PDF

Related posts:

  1. RGPV Define Mealy and Moore Machine
  2. RGPV TOC Short note on equivalent of DFA and NFA
  3. RGPV TOC What do you understand by DFA how to represent it
  4. RGPV short note on automata
  5. RGPV TOC properties of transition functions
  6. RGPV TOC What is Trap state
  7. CFL are not closed under intersection
  8. NFA to DFA | RGPV TOC
  9. Moore to Mealy | RGPV TOC PYQ
  10. DFA accept even 0 and even 1 |RGPV TOC PYQ
  11. Short note on automata | RGPV TOC PYQ
  12. DFA ending with 00 start with 0 no epsilon | RGPV TOC PYQ
  13. DFA ending with 101 | RGPV TOC PYQ
  14. Construct DFA for a power n, n>=0 || RGPV TOC
  15. Construct FA divisible by 3 | RGPV TOC PYQ
  16. Construct DFA equivalent to NFA | RGPV TOC PYQ
  17. CNF from S–>aAD;A->aB/bAB;B->b,D->d.
  18. NDFA accepting two consecutive a’s or two consecutive b’s.
  19. Regular expresion to CFG
  20. Regular expression to Regular grammar
  21. Grammar is ambiguous. S → aSbS|bSaS|∈
  22. leftmost and rightmost derivations
  23. Construct Moore machine for Mealy machine
  24. Design a NFA that accepts the language over the alphabet, Σ= {0, 1,2} where the decimal equivalent of the language is divisible by 3.
  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 which accept 00 and 11 at the end of a string
  51. DFA end with 1 contain 00 | RGPV TOC draw
  52. RGPV TOC design finite automata problems
  53. Minimization of DFA
  54. Construct NFA without ∈
  55. RGPV TOC PYQs
  56. Introduction to Automata Theory