Consider a machine for a pattern recognizer where the patter

Consider a machine for a pattern recognizer, where the pattern length is N, i.e., the machine outputs a 1 when the pattern p_1p_2 ... p_N is detected. Can you design the machine with N - 1 states? If yes, explain how. If no, how many states are needed? Your answer should clearly describe the states of the system.

Solution

Given that pattern recognizer which recognize the pattern to perform some action.

pattern means we have to match all cases there is no chance to skip meanwhile to perform some action.

If pattern length given is N we have to consider each part of pattern while we do recognize.

if pattern p1p2...pn looks like this then we have to check p1,p2,p3,,upto pn as well there is no other way to skip.

so,here we need n states each state represent as not matched like that if value acceped at that particular state then we have to move next state otherwise that state represents the value as not recognized..i.e,pattern not recognized.