Question

Let A be any language. Define $\mathbf{DROP}\mathbf{-}\mathbf{OUT}\mathbf{\left(}\mathbf{A}\mathbf{\right)}$to be the language containing all strings that can be obtained by removing one symbol from a string in A. Thus,$\mathbf{DROP}\mathbf{-}\mathbf{OUT}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{xz}\mathbf{\right|}\mathbf{xyz}\mathbf{\in }\mathbf{A}\mathbf{ }\mathbf{ }\mathbf{where}\mathbf{ }\mathbf{ }\mathbf{x}\mathbf{,}\mathbf{z}\mathbf{\in }{\mathbf{\sum }}^{\mathbf{*}}\mathbf{,}\mathbf{y}\mathbf{\in }\mathbf{\sum }\mathbf{\}}$ . Show that the class of regular languages is closed under the $\mathbf{DROP}\mathbf{-}\mathbf{OUT}$ operation. Give both a proof by picture and a more formal proof by construction as in Theorem 1.47.

Short answer

The class of regular languages is closed under $\mathrm{DROP}\_\mathrm{OUT}$operation.

Step-by-step solution

To Operation the DROP_ OUT

A is any language and $\mathrm{DROP}-\mathrm{OUT}\left(\mathrm{A}\right)=\left\{\mathrm{xz}\right|\mathrm{xyz}\in \mathrm{A} \mathrm{where} \mathrm{x},\mathrm{z}\in \sum *,\mathrm{y}\in \sum \}$.

We have to prove that the class of the regular languages closed under the $\mathrm{DROP}\_\mathrm{OUT}$ operation.

If A is a regular language, then $\mathrm{DROP}-\mathrm{OUT}\left(\mathrm{A}\right)$is also regular language.

We have to take that A is regular and we have to prove that the $\mathrm{DROP}-\mathrm{OUT}\left(\mathrm{A}\right)$is regular.

Since A is a regular language, it must be recognized by a DFA.

Let $M=\left(Q,\sum ,\delta ,q_0,F\right)$be the DFA that recognizes A.

To Construct the NFA

Now we will construct the NFA $N=\left(Q\text{'},\sum \cup \{\in \},\delta \text{'},q_0^{\text{'}},F\text{'}\right)$that recognizes $\mathrm{DROP}-\mathrm{OUT}\left(\mathrm{A}\right)$.

There are two copies of Machine M.

Copy 1:Copy 1 corresponds to the state of having ‘not yet skipped a symbol’

Copy 2:Copy 2 corresponds to the state of having “already skipped a symbol”.

(i) Proof by picture: -

$N=\left(Q\text{'},\sum \cup \{\in \},\delta \text{'},q_0^{\text{'}},F\text{'}\right)$

$Q=\left\{\left(q,b\right)\right|q\in Q,b\in \{0,1\}\}$= set of states

$q_0^{\text{'}}=$start state

$=\left({\mathrm{q}}_0,0\right)$

$\mathrm{F}\text{'}=$set of final states

$=\left\{\right(\mathrm{q},1|\mathrm{q}\in \mathrm{F}\}$.

$\text{δ'}$is gives as follows:

localid="1663243041084" $\to \delta \text{'}\left(\right(a,b),a)=\left\{\right(\delta (q,a),b\left)\right\}\forall q\in Q,b\in \{0,1\},a\in \sum$

This means that both the copy1 and copy2 of the machineMdo exactly as the original machine does on every symbol a of the alphabet

localid="1663243051646" $\to \delta \text{'}\left(\right(q,0),\in )=\left\{\right(\hat{q},1)\exists a\in \sum ,\delta (q,a)=\hat{q}\}$

Also at every stage, the machine has the option to skip a character. The only accepting sates are in copy 2. This means, the machine cannot accept a string without skipping a character.

To Proof the given length of the string

The formal proof is given by induction on the length of the string.

An appropriate inductive hypothesis is to assume that, for any string w of length k,

The machine M stays in the copy -1 if it has not yet skipped a symbol.

i.e. $\delta \text{'}*\left(\right(q_0,0),\omega )=(q_1,0) iff \delta (q_0,\omega )=q_1$

The machine M jumps to the copy-2 if there is some symbol a that is skipped.

i.e. $\delta \text{'}*\left(\right(q_0,0),\omega )=(q_1,1) if \delta (q_0,{\omega }_{1}a{\omega }_2)=q_1$ .

So, in both (i) and (ii) we constructed and NFAN that recognizes the language role="math" localid="1663242954164" $\mathrm{DROP}-\mathrm{OUT}\left(\mathrm{A}\right)$.

Thus $\mathrm{DROP}-\mathrm{OUT}\left(\mathrm{A}\right)$is regular.

Hence class of regular languages is closed under $\mathrm{DROP}-\mathrm{OUT}\left(\mathrm{A}\right)$operation.