Question

Draw finite state automata that accept the following, in each case also give a regular expression matching exactly the accepted strings:

a)all binary strings containing exactly three 0s.
b)all binary strings starting 010
c)all binary strings containing a substring 111
d)all binary strings ending 11 or 00
e)all binary strings containing 0's and 1's such that the number of 1's in the string is divisible by 3.

Answer 1

This response includes Finite State Automata and regular expressions for various patterns in binary strings.

Step-by-step explanation:

a) The finite state automaton for all binary strings containing exactly three 0s is as follows:

Regular expression: (1|01|001)*000(1|01|001)*

b) The finite state automaton for all binary strings starting with 010 is as follows:

Regular expression: 010(1|0)*

c) The finite state automaton for all binary strings containing a substring 111 is as follows:

Regular expression: (0|1)*111(0|1)*

d) The finite state automaton for all binary strings ending with 11 or 00 is as follows:

Regular expression: (0|1)*11|(0|1)*00

e) The finite state automaton for all binary strings containing 0's and 1's such that the number of 1's in the string is divisible by 3 is as follows:

Regular expression: ((0|(00|11)*1(00|11)*))*