Sheet 7: Question 3

Question

Question is :

Submit the solution in the following form:
labels 0:s1; 1:s2,s3; 2:; 3:s0,s1,s2; 4:s4;
unsafe 4;
init 0,1;
transitions (0,{a},,1); (0,{},,2); (1,{a},,3); (4,{a},,3); (3,{},,3);
accept 2;

Solution :

In the form to be Submitted  :

labels 0:s1,s3; 1:s0; 2:; 3:s0,s1; 4:s2; 5:s3; 6:s1;

unsafe 2;

init 0;

transitions (0,{},,1); (0,{a},,3); (3,{},,4); (3,{a},,1); (4,{},,5); (4,{a},,4); (5,{},,1); (5,{a},,6); (6,{},,2); (6,{a},,1); (1,{},,4); (1,{a},,2); (2,{},,2); (2,{a},,2);

accept 1,3,4;

In this, where is the error?

Answer 1

I don't find a real error in your computation, but you have not done what you should do (I will come to that later). 

First, I computed the same automaton; when using the input 

  inputs {a},{};
  init 1,3;
  transitions 
    (0,{},2);
    (1,{a},0);
    (2,{a},2); (2,{},3);
    (3,{a},1); (3,{},0);
  accept 0,2;

we obtain the following automaton (which is the given one):

You applied the Rabin/Scott construction to the above automaton and as far as I can say, you have done that correctly, at least I obtained the following similar deterministic automaton:

which is exactly what you had.

The exercise text is unfortunately somewhat broken, but it seems that it wants to you follow the idea to first make the given liveness automaton totally defined by adding a sink state so that then the Rabin/Scott construction can be applied. Adding such a sink state may change the language of the automaton, but you should not care about this and should still do that here.

So, the first step would be adding a sink state, which converts the given (partially defined) liveness automaton into the following one (where a sink state s4 has been added):

Is is encoded by the following text:

inputs {a},{};
init 1,3;
transitions 
  (0,{},2);  (0,{a},4);
  (1,{a},0); (1,{},4);
  (2,{a},2); (2,{},3);
  (3,{a},1); (3,{},0);
  (4,{a},4); (4,{},4);
accept 0,2;

To mimic the accepting paths of the given automaton we now have to use the acceptance condition that states that we should never be in the sink state s4, but we must at least once reach one of the states s0 or s2. 

Now you should apply the Rabin/Scott construction to the above automaton and the result should be submitted where the unsafe state should be the one that  corresponds with the sink state. I leave the rest up to you.

Comments

Comment: If you don't find bad characters, send a message to your tutor to check the input you have submitted.

---

I tried removing all breaks and unnecessary characters, but it is still not accepted in the tool.

---

Checking the expected answer in the online exercise system, I see now what the actual exercise should be. The given automaton in partially defined, and therefore we should not just apply the Rabin/Scott subset construction to determinize it. But we may first make the automaton totally defined in that we add a sink state where all missing transitions will target to. You should then apply the Rabin/Scott construction to the automaton that is completed this way. Please try this, and let me know whether that worked for you.

---

This still does not seem to work.I tried with the tool and created transitions to the sink state from all the  states for undefined inputs and created the Rabin/Scott determinization, but it is still not accepting the result. I have a different automata to start with but i think i did everything correct. Should i add another question with all the details?

---

Determinization Works. I tried to do it without the tool and then it worked for me. I do not know if i made some mistake in giving the input to the tool.

---

I also did without tool and verified it with tool as well. It is the same.
Can you please share your solution how you did it?

---

For me, the solution given by the tool was different so i cat say about that. What i did was introduce a new empty state and direct all missing transitions to that state. The perform the determinization as usual. I dont know how to reply with images and stuff, sorry about that. If possible, you could tell me that and i'd post a picture of my question and determinized automata

---

I think the exercise refers to slide 87 of the Omega-automata chapter. It discusses whether one can determinize a NDetF automaton using the Rabin/Scott construction by adding a sink state and then accepting only if that state is never reached while the previous accepting states have to be reached at least once. That does not work in general as explained on slide 87, but you should try this with the given automaton.