Thanks deepakk

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

Best answer

In any Directed Graph, like DFA or NFA, If we wish to find All the Reachable nodes(states) from some node(starting state) then we can just apply Breadth First Traversal or Depth First Traversal on that DFA or NFA from Starting State.

The Idea is that **Some State $Q$ is said to be Reachable in any DFA or NFA Iff there is Some Path/walk from Starting state to that state $Q$. **

Since, Every Walk contains a Path. We can simply remove Walk from above theorem.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,260 answers

182,164 comments

67,679 users