Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Problem 1.40.

a. Show that the class of CFLs is not closed under NOPREFIX.

b. Show that the class of CFLs is not closed under NOEXTEND.

Problem 1.40.

Recall that string x is a prefix of string y if a string z exists where xz = y, and that x is a proper prefix of y if in addition x ≠ y. In each of the following parts, we define an operation on a language A. Show that the class of regular languages is closed under that operation.

^Aa. NOPREFIX(A) = {w ∈ A| no proper prefix of w is a member of A}.

b. NOEXTEND(A) = {w ∈ A|w is not the proper prefix of any string in A}.