Question

Consider the language ODDNOTAB consisting of all words that do not contain the substring ab and that
are of odd length.

Give
(i) an applicable universal set,
(ii) the generator(s),
(iii) an applicable function on the universal set and
(iv) then use these concepts to write down a recursive definition for the language.

Answer 1

(i) The set {a.b}* is an applicable universal set.

(ii) a and b are the generators.

(iii) The concatenation function is applicable on the universal set.

(iv) The following is a recursive defintion of ODDNOTAB:

ODDNOTAB is the smallest subset of {a.b}* that satisfies the following conditions:

• a and b belong to ODDNOTAB
• if w belongs to ODDNOTAB, then bb.w and w.aa also belong to ODDNOTAB
• if w belongs to ODDNOTAB and does not end with an a then w.ba and w.bb belong to ODDNOTAB
• if w belongs to ODDNOTAB and does not begin with b then aa.w and ba.w belong to ODDNOTAB