in Theory of Computation
2,236 views
1 vote
1 vote
If two finite state machines M and N are isomorphic then M can be transformed to N by relabeling

(a) the states alone

(b) the edges alone

(c) both the states and edges

(d) none of the above
in Theory of Computation
2.2k views

4 Comments

isomorphic means equivalent, ( as per my knowledge )

The Question now

If two finite state machines M and N are equivalent then M can be transformed to N by relabeling

states only. (already edges are in correct way)

1
1
both state and edge

because

let in M edge label (transition) define such as a,b,c  but in N it may be different such as x,y,z (but M and N both are isomorphic because isomorphic does not care about label) so we have to change the label

for state explanation

no of final state in M and N can be different means m can have 2 but N can have 3 etc but both are isomorphic

we have to change them
0
0

let in M edge label (transition) define such as a,b,c  but in N it may be different such as x,y,z (but M and N both are isomorphic because isomorphic does not care about label) so we have to change the label

therefore input alphabet of M and N are not same, then  how can we say those are isomorphic ?

 

no of final state in M and N can be different means m can have 2 but N can have 3 etc but both are isomorphic

if no.of states are not equal, then relabeling is not work,

note that re-labeling means, just changing the names but not no.of states

0
0
@ Shaik masthan

i have taken the isomorphic means diagram of this two FSM is isomorphic

which seem to be wrong but according to u

you have taken its meaning equivalent

i think i am wrong
0
0

1 Answer

0 votes
0 votes
option a is correct.

explanation :

if you renumber the states of one automata, you get the 2nd automata . So the two automata are identical up to renumbering.

Related questions