Now given the recognized string contains M characters eg 10

Now, given the recognized string contains M characters (e.g., \'10\' has two characters in (2)) and the count of the recognized string is N (e.g., twice in (2)), at least how many states is needed to recognize the string in an FSM? Please justify.

Solution

Given that:

the recognized string contains M characters, and the count of recognized string is N, then atleast (M*N)+1 states are needed to recognize the string in an FSM

explanation:

1)To recognize string of length M, it requires at least M+1 states in FSM

2)how, the count of recognized string is set as N, means the length of new string is M*N atleast..

so , to recognize string with length M*N ..is

at least (M*N)+1 states