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

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes

In the below question-

How does {} considered as the unsafe state?

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

1 Answer

0 votes
 
Best answer
G-properties are also called “safety properties”. Hence, a path touching a state not satisfying p violates our safety property. That's why one my want to call this state unsafe. Removing states not satisfying the G property from a G-automaton doesn't restrict their set of accepting run. Thus, this simplification is possible.

Not answering your question but still interesting: Unsafe states are highly misleading when trying to do subset construction on NDetG-automata. Just think of an example similar to the one here but with an edge labeled a from the unsafe state back to the initial state, and the edge from initial to unsafe would be labeled !a. Of course, all paths using this edge shouldn't be accepted as they are in the initial state. And of course, there is no accepting path with the same label because our only safe state {p} has a self-loop only annotated by !a. But if we applied subset right away, we'd have {{p}} and {{p},{}} (and a fail-state). Both {{p}} and {{p},{}} would be accepting as they both contain the accepting state {p}. But the tricky thing happens when we read a. That leads us from {{p},{}} to {p} as there is an edge from {} to {p} labeled a. Do you see the subtle problem? The result of the subset construction now contains a an accepted path wouldn't be accepting in the original. A path of accepting states in the subset result just means that for every prefix of this path, there is path to an accepting state. It does not mean that there is a path in the original automaton that only consisted of accepting states.
by (25.6k points)
selected by

Related questions

0 votes
1 answer
0 votes
1 answer
asked Jan 13, 2021 in * TF "Emb. Sys. and Rob." by MS (1.1k points)
0 votes
1 answer
0 votes
1 answer
0 votes
2 answers
asked Jan 15, 2021 in * TF "Emb. Sys. and Rob." by MS (1.1k points)
Imprint | Privacy Policy
...