Consider the deterministic finite automaton M with states S = {so, $1,..., 87}, start state so,...

 

Transcribed Image Text:

Consider the deterministic finite automaton M with states S = {so, $1,..., 87}, start state so, single accepting state s6, and alphabet = {0, 1}. The following table describes the transition function T: SX S. State SO $1 82 $3 S4 85 86 S7 01 S7 $1 82 87 87 $3 83 $4 S5 $4 $3 $6 $5 $4 S7 S7 i. Draw the transition diagram for M. ii. Let U = {101001101, 101100}. For each u EU describe the run for input u to M. Does M accept u? iii. Describe the language recognised by M. (b) Construct a finite-state machine which accepts a string w of 0s and 1s if and only if w contains the substring 1010. Activate W Consider the deterministic finite automaton M with states S = {so, $1,..., 87}, start state so, single accepting state s6, and alphabet = {0, 1}. The following table describes the transition function T: SX S. State SO $1 82 $3 S4 85 86 S7 01 S7 $1 82 87 87 $3 83 $4 S5 $4 $3 $6 $5 $4 S7 S7 i. Draw the transition diagram for M. ii. Let U = {101001101, 101100}. For each u EU describe the run for input u to M. Does M accept u? iii. Describe the language recognised by M. (b) Construct a finite-state machine which accepts a string w of 0s and 1s if and only if w contains the substring 1010. Activate W

Answer rating: 100% (QA)

a i Transition diagram for the deterministic finite automaton M 0 1 SO 1 2 3 4 5 6 7 S7 1 7 2 7 3 S4 ii For each input string u U 101001101 101100 we ... View the full answer