1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?