Question

Need help with Finite State Automata

Answer 1

I need help with the last question

Answer 2

@KingGeorge can you help me?

Answer 3

I can't say I'm familiar with this stuff to help. However, could you tell me how to determine if two automata are equivalent?

Answer 4

yaa wait a sec sorry abt that i was just afk

Answer 5

well its basically showing that the

Answer 6

2 automata r equal. this is done by finding the equivalence classes of each and when u draw the diagram they r bth the same

Answer 7

I'm still thinking about this. Can you tell me which nodes in the automaton on the right are final nodes?

Answer 8

I believe \(S_2\) and \(S_4\) are final correct?

Answer 9

*on the left, not right.

Answer 10

ohh u mean accepting states??? yaa its s_2 and S_4

Answer 11

waiittt the left its S_2 and S_4 and the right its just S_4 i think

Answer 12

Give me a few more minutes.

Answer 13

Alright, so I think I've found the minimum of both of the automata. So now, if they're equivalent the graphs will look the same, and if they're not equivalent, the graphs will look different. Is this correct?

Answer 14

yaaaaaa

Answer 15

And if they look the same except for a number or two, they're still different correct?

Answer 16

When you are done with this problem, KingGeorge, could you possibly help me out with a

Geometry problem?

Answer 17

yes they have to have the same diagram

Answer 18

In that case, I believe they are not equivalent.

Answer 19

My brain is fried idk abt urs lol. hahahahah
U r always on here. i am assuming that if it isnt ur own work its not as stressful loil

Answer 20

For the one on the left, I have equivalence classes are {0,1}, {2,4}, {3} with the {2,4} node being the accepting/final node, and {0,1} the beginning. There are arrows labeled "0" from {0,1} to {3}, from {3} to {2,4}, and from {2,4} to {0,1}. There are arrows labeled "1" from {0,1} to {2,4}, from {3} to {0,1}, and from {2,4} to {2,4}.

For the one on the right, I have equivalence classes of {0,2}, {1,3},{4} with the {4} node being the accepting/final node, and {0,2} the beginning. There are arrows labeled "0" from {0,2} to {4}, from {1,3} to {0,2}, and from {4} to {0,2}. There are arrows labeled "1" from {0,2} to {1,3}, from {1,3} to {4}, and from {4} to {4}.

There are a couple differences. In the chart on the left, we have an arrow labeled "1" going from the start node to the finish node, on the right, this arrow is labeled "0."

Also from the non start/finish node on the left, there is an arrow labeled "0" to the finish. On the right, it's labeled "1."

Answer 21

okkkk so when u graph the equivalence classes like the diagram of both do u get the same graph? no right

Answer 22

No, some of the arrows are labeled differently.

Answer 23

okkk gotcha thankd king that was realllllllyy niiiccceeee offff uuuuu to sit on my problemmmmm

Answer 24

You're welcome.

btw, I was able to do this thanks to the explanation and example of this thing over here.
http://www.informatik.uni-bremen.de/agbs/lehre/ss05/pi2/hintergrund/minimize_dfa.pdf

Answer 25

ohh thanks for this linkkk ill save it on my comp thannkksss

Answer 26

you're welcome :)