Question

Draw a deterministic finite state machine for the input alphabet A where A = {1, 2, 3, 4, 5} that recognises exactly all strings that include the 2 letter string 42 exactly once. For example, the machine will accept the string 54214 but reject the strings 432 and 421421.

Answer 1

The task is to construct a DFA(deterministic finite state) machine for the the input alphabet A = {1,2,3,4,5} that recognises exactly strings that include string "42" exactly once.

Alphabet A = {1,2,3,4,5}

The above DFA has been constructed using a simulator for better understanding.

Here "start" is the starting state.

"s1", "s2" are the accepting states.

"s3" is the dead state.

TRANSITION TABLE

	1	2	3	4	5
start	start	start	start	s0	start
s0	start	s1	start	s0	start
s1	s1	s1	s1	s2	s1
s2	s2	s3	s2	s2	s2
s3	s3	s3	s3	s3	s3