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.

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.

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.

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.