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

557 users

0 votes

Referring to the below breakpoint construction : 

How does it have a path from accepting state ({p,q}, {p}) back to q with input (!a & !b)?

in * TF "Intelligent Systems" by (1.1k points)

1 Answer

0 votes
 
Best answer
You are talking about the dark grey state {{q}, {p,q}}{{p,q}} and its transition labeled !a&!b, right?

The oiginal automaton knows two states: {q} and {p,q}. After reading !b, we go non-deterministically to either of them. That's what the grey state is representing. The two states differ in the inputs for which they have transitions. {q} requires !b, {p,q} is stricter and requires specifically a&!b. That's where the case distinction in the grey state comes from. If we read a&!b, we can takes all transitions of {q} (since we satisfy !b) as well as the transition from {p,q} (which doesn't add more successor states). Hence, a&!b leads to a self-loop in the grey state. For b, we have no transitions anywhere and move to the fail state. It remains to consider !a&!b. Here, the only transitions are ones of {q}.

The second set in the tuple is the set of accepting successors of the previous second set. As the previous second set contains only {p,q}, which has no successors for !a&!b, the second set is empty in the next state. The first set should (after the standard procedure) be {{q},{p,q}} as we can reach both reading !b in {q}. Apparently, the creator of the suggested solution has merged this newly created state {{q}, {p,q}}{} to {{q}}{}. You can try to convince yourself that this optimization neither adds nor removes accepting runs. However, it is not the standard procedure we taught in class.

tl;dr: The loop back is more like “ah, snap, we should have non-deterministically stayed in the initial state as we can't close the loop of the accepting state here”.
by (25.6k points)
selected by
Imprint | Privacy Policy
...