- #1

0rthodontist

Science Advisor

- 1,230

- 0

The other problem is:

Present and justify an algorithm that decides whether a finite automaton M = (Q, sigma, delta, q0, F) recognizes the language sigma*, in time O(|Q| x |sigma|). Hint: Read the section of the notes that proves the regular languages are closed under the Boolean operations

The way I solved this was by disregarding the hint and simply searching M for any nonaccepting states reachable from q0, and I got full credit. But this current question I am working on seems to depend on this one. Does anyone have an idea about what the hint means?