Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finite Automata

  1. Mar 8, 2006 #1


    User Avatar
    Science Advisor

    There is a problem on the latest homework that I am struggling with. From the way the problem is worded, I am pretty sure that the key to solving this problem is the same as the hint on a problem on the last homework. However when I did that other problem, I ignored the hint, and now I am having difficulty figuring this one out. Because I don't want to do anything that might be regarded as illicit, I'll only give the other problem:

    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?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?