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

Two definition of sets of all strings and sets of odd length binary are given

Explanation:

A.) Suppose A is the string of contain at least one a:A = a

B will be same as it is b:B = b

Sets of the union of the AB and BA in which A followed B and corresponding B will follow A. Set = will (AB) (BA) = (*a*, *b*) (*b*, *a* )….

B.) There is the regular expression is compared with two 00 which is surrounded by the 0+1 that accepted at least two 0s.