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

Answer :-

I have converted the given automation in deterministic form as follows :

inputs a,;

outputs ;

init 1,3;

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

accept 0,2;

Then applied Rabin/scott algorithm as follows:

The output is :

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

unsafe 6;

init 0;

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

accept 1,2,3;

But it is also wrong.

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

1 Answer

0 votes
 
Best answer

The first automaton above is not deterministic; I guess you mean that it is total (I don't want to be picky, it is just to clarify). It has been obtained by completing the following automaton:

to this one (which is exactly what you did):

You apply the Rabin/Scott construction to this automaton, and you obtain the one below:

Here, I am confused: The above automaton is described as follows:

labels 0:s1,s3; 1:s0,s1; 2:s0,s4; 3:s2,s4; 4:s3,s4; 5:s1,s4; 6:s4;
unsafe 6;
init 0;
transitions 
    (0,{a},,1); (0,{},,2);
    (1,{a},,2); (1,{},,3);
    (2,{a},,6); (2,{},,3);
    (3,{a},,3); (3,{},,4);
    (4,{a},,5); (4,{},,2);
    (5,{a},,2); (5,{},,6);
    (6,{a},,6); (6,{},,6);
accept 1,2,3;

Your image matches with this automaton and is therefore correct, I would say. However, your input has the following problem (and I don't know whether that caused the rejection:)

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

So, you listed state s4 twice for the label of superstate 6. Apart from this, I don't see what else would be wrong. It is annoying if that is the reason for rejection, and therefore we will give you the points for this exercise that you definitely deserve!

BTW: Checking the submissions, I have seen that the above was not the problem. Before you submitted that solution you had a correct version, where the label of superstate 6 was correct also. However, you have submitted the first correct solution exactly after the system gave you another example. It seems that you have not realized that and continued with the solution to the previous example. That was the final problem at the end.

by (170k points)
selected by

Related questions

0 votes
1 answer
asked Jun 18, 2020 in * TF "Emb. Sys. and Rob." by MS (1.1k points)
0 votes
1 answer
asked Jun 13, 2020 in * TF "Vis. and Sci. Comp." by nafisur (300 points)
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy
...