Question

2. Give recursive definitions for the following sets. a. The set of all strings over {a, b} containing at least one "a". b. The set of odd-length binary strings that end with 00.

Answer 1

Answer and explanation:

Recursive is related to repeat the definition, rule, and procedure.

a) The set of all strings over {a,b} containing at least one a.

Let x is a string containing at least one a: x=a and y= b

Sets of union of XY and yx will be (XY) (yx) = (a,b) (b, a)

b) The set of odd length binary strings that end with 00

There is a regular expression compared with two 00, which is surrounded by 0+1 with at least two 0s.