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

Hello,

I have following queries regarding determinization of automata of part (a) in (b). 

  • In my solution there is a transition marked in red. Can you please explain why it is not there in the exam solution?
  • You can clearly see there are two Accepting states in my solution, because S3 is present in both two of these. In the exam solution there is only one. Why the other one is not marked as accepting state?
  • Lastly, we can have a sync state as well. In the exam solution it is not drawn. So is it optional? Our solution is considered correct even if we don't draw it?


My solution:

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

1 Answer

0 votes
The solution given for the exam ist correct, and yours is unfortunately wrong. To compute the transitions of state ({s2,s3},{s3}), we have to consider the transitions from states s2 and s3 which are as follows: s2--*-->s2, s2--*-->s3 and s3--!b-->s3. Hence, with input !b (regardless of a), we have ({s2,s3},{s3}) --!b--> ({s2,s3},{s3}) and with input b (again regardless of a), we have ({s2,s3},{s3}) --b--> ({s2,s3},{}) since we have to compute the existential successors in both components, and have to intersect the second component with {s3}.

It is easily seen that your solution cannot be correct, since your automaton is not deterministic. Note that a and b are boolean variables that symbolically encode the four inputs !a&!b, !a&b, a&!b, and a&b. Having outgoing transitions for a as well as for condition b (and !b) gives us choices for the input a&b: Since a holds, we could remain in state ({s2,s3},{s3}) of your automaton, and since b holds, we may switch to state ({s2,s3},{}). Hence, your automaton is not deterministic, and can therefore be not a correct result of a determinization procedure.

Accepting states of the automaton are those where the second component is not empty. That is only the case for state ({s2,s3},{s3}) and in particular not for state ({s2,s3},{}).

I think that you mean a sink state instead of a sync state. But why should we have a sink state? It can be generated by the determinization procedure if needed, but it is not generated here, since it is not needed here.
by (170k points)

Related questions

Imprint | Privacy Policy
...