CODEWITHSUNDEEP
mathcomputer-sciencenfaautomatoncomputer-science-theory
Hans von Olo
Hans von Olo

Reputation: 21

Determining whether a nondeterministic finite automaton accepts every possible string

Given an NFA, is there a way to determine whether it accepts all strings constructed from its alphabet, without having to iterate over the infinite set of possible strings?

Upvotes: 2

Views: 888

Answers (1)

templatetypedef
templatetypedef

Reputation: 373462

Sure! Here's one algorithm:

  1. Run the subset construction to turn the NFA into a DFA.
  2. Minimize the DFA using a DFA minimization algorithm.
  3. Check whether the DFA consists of a single state that's accepting. If so, the original NFA accepts everything. If not, there's at least one string the NFA doesn't accept.

There may be a faster algorithm than this (step (1) could take time exponential in the size of the input NFA), but this shows that there is indeed some algorithm for solving this problem.

Upvotes: 2

Related Questions