Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


529 users

0 votes

In the solution [Link here], 

The acceptance condition of the automaton is changed to FG and then breakpoint construction is applied. Although, we also have another method to determinize it by totaling the NDetF(partial) and then applying subset construction which does not always work.

How do we know before applying the subset construction that it will not work for the given automaton?

in * TF "Emb. Sys. and Rob." by (640 points)

1 Answer

+1 vote
Best answer
That question is discussed on pages 90-91 of the related chapter in the lecture slides. In general, if the language of the automaton does not change when making it totally defined, then you can work with the subset construction afterwards. Whether that is the case, is not that easy to check in general, but in many cases, it can be easily seen. The safe way that always works is the way over NDetFG and the breakpoint construction.
by (166k points)
selected by
Imprint | Privacy Policy