UGC NET JULY 2018 (Computer Science And Applications Paper-II) (Question 31)
Q 31. Two finite state machines are said to be equivalent if they :
Answer : 3. Recognize the same set of tokens
Q 31. Two finite state machines are said to be equivalent if they :
- Have the same number of edges
- Have the same number of states
- Recognize the same set of tokens
- Have the same number of states and edges
Answer : 3. Recognize the same set of tokens
Two finite state machine are said to be equivalent if, starting from their respective initial states, they will produce the same output sequence when they are given the same input sequence. That implies they must recognize the same set of tokens.
Definition 1 (equivalence of finite state machines): Two finite state machines M1 and M2 are
equivalent (M 1 E M2) if they have the same input and output alphabets and if, starting from
their respective initial states, they produce the same output for any input string.
Definition 2 (equivalence of states): Two states p (of finite state machine M1) and q (of
machine M2, which may or may not be the same as M1) are equivalent (p 5 q) if the machines
they belong to have the same input and output alphabets and if, for any input string, machine M1
started from state p produces the same output as machine M2 started from state q.
Definition 3 (strongly connected machines): A finite state machine M is strongly connected if,
for any states 3 and r in the state space of M, there exists a finite sequence of transitions that
takes M from state 3 to state r.
Definition 1 (equivalence of finite state machines): Two finite state machines M1 and M2 are
equivalent (M 1 E M2) if they have the same input and output alphabets and if, starting from
their respective initial states, they produce the same output for any input string.
Definition 2 (equivalence of states): Two states p (of finite state machine M1) and q (of
machine M2, which may or may not be the same as M1) are equivalent (p 5 q) if the machines
they belong to have the same input and output alphabets and if, for any input string, machine M1
started from state p produces the same output as machine M2 started from state q.
Definition 3 (strongly connected machines): A finite state machine M is strongly connected if,
for any states 3 and r in the state space of M, there exists a finite sequence of transitions that
takes M from state 3 to state r.
0 comments:
Post a Comment