Question

We define the avoids operation for languages A and B to be

$\mathbf{A}\mathbf{}\mathbf{avoids}\mathbf{}\mathbf{B}\mathbf{=}\mathbf{\left\{}\mathbf{w}\mathbf{\right|}\mathbf{w}\mathbf{\in }\mathbf{A}\mathbf{}\mathbf{and}\mathbf{}\mathbf{w}\mathbf{}\mathbf{doesn}\mathbf{’}\mathbf{t}\mathbf{}\mathbf{contain}\mathbf{}\mathbf{any}\mathbf{}\mathbf{string}\mathbf{}\mathbf{in}\mathbf{}\mathbf{B}\mathbf{}\mathbf{as}\mathbf{}\mathbf{a}\mathbf{}\mathbf{substring}\mathbf{\}}\mathbf{.}$

Prove that the class of regular languages is closed under the avoids operation.

Short answer

$\mathrm{A}\mathrm{avoids}\mathrm{B}=\left\{\mathrm{w}\right|\mathrm{w}\in \mathrm{A}\mathrm{and}\mathrm{w}\mathrm{doesn}’\mathrm{t}\mathrm{contain}\mathrm{any}\mathrm{string}\mathrm{in}\mathrm{B}\mathrm{as}\mathrm{a}\mathrm{substring}\}$ the class of regular languages is closed under the avoids operation is proved.

Step-by-step solution

Regular language.

A language is regular if it can be expressed in terms of regular expression. A regular expression can also be described as a sequence of pattern that defines a string. Regular expressions are used to match character combinations in strings.

Avoids operation for regular language.

$\mathrm{A}\mathrm{avoids}\mathrm{B}=\left\{\mathrm{w}\right|\mathrm{w}\in \mathrm{A}\mathrm{and}\mathrm{w}\mathrm{doesn}’\mathrm{t}\mathrm{contain}\mathrm{any}\mathrm{string}\mathrm{in}\mathrm{B}\mathrm{as}\mathrm{a}\mathrm{substring}\}$

Firstly define$\mathrm{A}\mathrm{avoids}\mathrm{B}$ as$(\mathrm{A}-(\mathrm{A}\mathrm{has}\mathrm{B}\left)\right)$ , where $\mathrm{A}\mathrm{has}\mathrm{B}$are strings of $\mathrm{A}$which contain strings of $\mathrm{B}$as substrings.

Then $\mathrm{A}\mathrm{avoids}\mathrm{B}$will be strings of $\mathrm{A}$that do not contain strings of $\mathrm{B}$as substrings.

Define $\mathrm{A}\mathrm{has}\mathrm{B}$ as $\mathrm{A}\cap (\mathrm{\Sigma }*\mathrm{B}*)$. Then$\mathrm{A}\mathrm{has}\mathrm{B}$ are strings of $\mathrm{A}$which contain strings of $\mathrm{B}$as substrings.

Thus here also have $\mathrm{A}\mathrm{avoids}\mathrm{B}$$\mathrm{A}-(\mathrm{A}\cap ({\mathrm{\Sigma }}^{*}{\mathrm{B\Sigma }}^{*}\left)\right)$

Since, regular languages are closed under concatenation, intersection, and subtraction they are also closed under operation avoid.

Here the regular language follows the property of avoid if it can be expressed in terms of regular expression.A regular expression can also be described as a sequence of pattern that defines a string. Regular expressions are used to match character combinations in strings.

Hence, $\mathrm{A}\mathrm{avoids}\mathrm{B}=\left\{\mathrm{w}\right|\mathrm{w}\in \mathrm{A}\mathrm{and}\mathrm{w}\mathrm{doesn}’\mathrm{t}\mathrm{contain}\mathrm{any}\mathrm{string}\mathrm{in}\mathrm{B}\mathrm{as}\mathrm{a}\mathrm{substring}\}.$the class of regular languages is closed under the avoids operation is proved.