Finite Automata

  • #1
0rthodontist
Science Advisor
1,230
0
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?
 

Answers and Replies

Related Threads on Finite Automata

Replies
0
Views
2K
  • Last Post
Replies
3
Views
835
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
23
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
756
Top