The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
43 views
1.How to identify the reachable state in NFA or DFA.
asked in Theory of Computation by Junior (755 points) | 43 views

1 Answer

+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.

answered by Boss (19.4k points)
selected by
0
Thanks deepakk

Related questions

0 votes
1 answer
3
asked Nov 3 in Theory of Computation by Na462 Loyal (6.9k points) | 38 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,572 questions
48,562 answers
155,425 comments
63,581 users