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


510 users

0 votes
I have some general doubts regarding automaton's determinisation.

1) NDetG -> DetG => By removing all unsafe states, then use subset construction.

 If the NDetG not fully defined also can we proceed like this? Or should we add a sink state?

2) NDetF partial , to determinise this, can we add a sink state then use subset construction?

 Or should we convert F to FG then use breakpoint?
in # Study-Organisation (Master) by (2.7k points)

1 Answer

+1 vote
Best answer
For NDetG -> DetG, you can always use the subset construction after removing the unsafe states.

For NDetF, that is not always possible, at least it works for totally defined automata, and sometimes also for others, which is however not that easy to decide. The safe way for NDetF is therefore to convert it to NDetFG and to use the breakpoint construction to get a DetFG automaton. Note that some NDetF automata do not have equivalent DetF automata at all.
by (162k points)
selected by
Yeah.. I understood. If it's fully defined also I can convert to NDetFG then breakpoint to get DetFG, that's also a valid case right?
Sure, that is always the safe way!
Thanks for the clarification. I understood it.

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy