Question

Recall that string x is a prefix of string y if a string z exists where $\mathbf{xz}=\mathbf{y}$, and that x is a proper prefix of y if in addition $\mathbf{x}\mathbf{6}=\mathbf{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.

$$\begin{gathered} \mathbf{a}\mathbf{)}\mathbf{}\mathbf{NOPREFIX}\left(\mathbf{A}\right)=\{\mathbf{w}\in \mathbf{A}\left|\mathbf{no}\mathbf{proper}\mathbf{prefix}\mathbf{of}\mathbf{w}\mathbf{is}\mathbf{a}\mathbf{member}\mathbf{of}\mathbf{A}\right\}. \\ \mathbf{b})\mathbf{NOEXTEND}\left(\mathbf{A}\right)=\{\mathbf{w}\in \mathbf{A}\left|\mathbf{w}\mathbf{is}\mathbf{not}\mathbf{the}\mathbf{proper}\mathbf{prefix}\mathbf{of}\mathbf{any}\mathbf{string}\mathbf{in}\mathbf{A}\right\}. \end{gathered}$$

Short answer

$NOEXTEND\left(A\right)$is also regular.

Step-by-step solution

To Prefix of string operationa) NOPREFIXA = {w∈A| no proper prefix of w is a member of A}.

a)$NOPREFIX\left(A\right)=\left\{w\in 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,\sum ,\delta ,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\in \sum ^{*}:x\in A \text{and} z\in \sum ^{*} \text{such} \text{that} xz=y\right\}$.

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

$Q^1=Q\cup \left\{q_f\right\}$and $q_f\notin Q$

For $q\notin Q^1$and $a\in \sum$define

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

Step 2:To Prefix of string operation b) NOEXTEND(A) = {w∈A| w is not the proper prefix of any string in A}.

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\cap \overline{L}$and class of regular languages are closed under intersection and complement, NOPREFIX (A) is also regular.

To Simplify the DFA language

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

Let$M=\left(Q,\sum ,\delta ,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\in F$, check whether there is a path from$q\in Q$ to any state inF(or a cycle involvingq) using Depth First Search.

Let$F^1\subseteq 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.