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

Hello,

Could you help me with construction of F automata from FG automata as shown in the screenshot below.

in * TF "Intelligent Systems" by (350 points)

1 Answer

+1 vote

The original automaton did not have state s1', and instead accepted all words having a run that eventually stays in states {s0,s1}. Hence, after some time, we should not use the transition s1->s3 any more, since we should stay in {s0,s1} after some time. The same can be achieved with the modified automaton where a copy of state s1 was made as shown above. You can now see that the following is equivalent for any word 

(1) the word has a run in the original automaton that eventually stays in states {s0,s1}

(2) the word has a run in the modified automaton that reaches state s1'

For (1)->(2), you just use the run of the original automaton until the point of time where states {s0,s1} are entered, but never left again. Instead of switching from s0->s1 you then switch to s0->s1'. For (2)->(1) it is even simpler; just use the run of the modified automaton but replace s1' by s1.

by (170k points)
Thank you :)

Related questions

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy
...