91Ó°ÊÓ

a)$NOPREFIX\left(A\right)=\left\{w∈A|\text{no} \text{proper} \text{prefix} \text{of} \text{w} \text{is} \text{a} \text{member} \text{of} \text{A}\right\}$

Let$M=\left(Q,∑,\mathrm{δ},q_o,F\right)$be a DFA recognizing .

Initially, find all words that have a proper prefix in A. The language L is represented as

$L=\left\{w∈\stackrel{*}{∑}:x∈A \text{and} z∈\stackrel{*}{∑} \text{such} \text{that} xz=y\right\}$.

Now, construct the NFA $M^1=\left(Q^1,∑,{\mathrm{δ}}^1,q_0^1,F^1\right)$for all its components such that:

$Q^1=Q∪\left\{q_f\right\}$and $q_f∉Q$

For $q∉Q^1$and $a∈∑$define

$$\begin{gathered} q_o^1=q_o \\ {F}^1=q_f \end{gathered}$$

If w is a string in Language L, there is a string y in A. Here, x is a proper prefix of y such that$xz=yandx$ is non-empty.

Ifwis taken as input of $M^1$, the computation on x ends at an accepting state in $M$ and some computation$z$ on ends at state$q_f$

So,wis accepted by $M^1$, which means that there is a computation that ends at $q_f$.

From the construction of $M^1$, the computation arrives at one of the accepting states in M before it reaches $q_f$.

As, NOPREFIX (A) is defined as$Aâˆ\copyright \stackrel{¯}{L}$and class of regular languages are closed under intersection and complement, NOPREFIX (A) is also regular.

b)$NOEXTEND\left(A\right)=\left\{w∈A|w \text{is} \text{not} \text{proper} \text{prefix} \text{of} \text{anystring} \text{in} \text{A}\right\}$

Let$M=\left(Q,∑,\mathrm{δ},q_o,F\right)$ be a DFA recognizingA.

Assume that the DFA for language M accepts that only the strings reaching the final state but not those strings that are added to reach a final state again.

So, the strings exactly ending in final states are accepted.

For a state $q∈F$, check whether there is a path from$q∈Q$ to any state inF(or a cycle involvingq) using Depth First Search.

Let$F^1⊆F$ be the set of all the states from which there is no such path.

Now, changing the set of final states$F$ to$F^1$ gives a DFA forNOEXTEND(A).

Thus, NOEXTEND(A) is also regular.