Question

a. Let $\mathbf{A}$be an infinite regular language. Prove that$\mathbf{A}$ can be split into two infinite disjoint regular subsets.

b. Let$\mathbf{B}\mathbf{and}\mathbf{D}$ be two languages. Write $\mathbf{B}\mathbf{\subset }\mathbf{\subset }\mathbf{D}\mathbf{if}\mathbf{B}\mathbf{\subseteq }\mathbf{D}$and $\mathbf{D}$contains infinitely many strings that are not in $\mathbf{B}$. Show that if $\mathbf{B}$and$\mathbf{D}$ are two regular languages where$\mathbf{B}\mathbf{\subset }\mathbf{\subset }\mathbf{D}$ , then we can find a regular language$\mathbf{C}$ where $\mathbf{B}\mathbf{\subset }\mathbf{\subset }\mathbf{C}\mathbf{\subset }\mathbf{\subset }\mathbf{D}$.

Short answer

a). $\mathrm{A}$can be split into two infinite disjoint regular subsets is proved.

b). $\mathrm{B},\mathrm{C},\mathrm{D}\mathrm{holds}\mathrm{B}\subset \subset \mathrm{C}\subset \subset \mathrm{D}$is holds regular language.

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.

A is split into two infinite disjoint regular subsets.

a).

An infinite regular language must be having a loop in its transition diagram for DFA deterministic finite automaton (if complement operation is not given). After that unroll the loop to make two DFA deterministic finite automatons, 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.

At the first of which accepts strings which have odd number of iterations of concerned loops and second accepts strings which have even number of iteration of concerned loops.

Since $\mathrm{A}$ is infinite and regular language, then the pumping lemma holds. And also have a pumping length $\mathrm{p}\ge 0$ for this language. And then take one word $\mathrm{w}\mathrm{in}\mathrm{A}$ such that $\left|\mathrm{w}\right|\ge \mathrm{p}$and according to the pumping lemma we split it into $\text{|w|}\ge \text{p}$as in the lemma.

Then, define the two languages like this:

${\mathrm{A}}_1$contains all the strings${\mathrm{xy}}^{2\mathrm{i}}\mathrm{z},\mathrm{i}\ge 0$.

${\mathrm{A}}_2$contains all the strings${\mathrm{xy}}^{2\mathrm{i}+1}\mathrm{z},\mathrm{i}\ge 0$.

That means that ${\mathrm{A}}_1$contains all the strings that go an even number of times in that cycle, and A2A2 all the strings that go an odd number of times in that cycle.

Hence,$\mathrm{A}$ can be split into two infinite disjoint regular subsets is proved.

It holds regular language or not.

b).

Here as given in the question$\mathrm{B}\subset \subset \mathrm{D}$ be two languages. $\mathrm{B}\subset \subset \mathrm{D}\mathrm{if}\mathrm{B}\subseteq \mathrm{D}$and$\mathrm{A}$ contains infinitely many strings that are not in $\mathrm{A}$. Show that if $\mathrm{A}$and$\mathrm{B}\subset \subset \mathrm{C}\subset \subset \mathrm{D}$ are two regular languages where, $\mathrm{B}\subset \subset \mathrm{D}$, then we can find a regular language $\mathrm{A}$where $\mathrm{B}\subset \subset \mathrm{C}\subset \subset \mathrm{D}$.

By partrole="math" localid="1660752008664" $\left(a\right)$ it can be always split $\mathrm{D}\mathrm{into}\mathrm{B}\mathrm{and}\mathrm{A}$which both are infinite and disjoint regular subsets.

And through this similarly, it can splits $\mathrm{A}\mathrm{into}{\mathrm{A}}_1\mathrm{and}{\mathrm{A}}_2$, both of them is regular infinite and disjoint.

Consider,$\mathrm{C}=\mathrm{B}\cup {\mathrm{A}}_1$ . Of course$\mathrm{C}$ is regular (then the union of the two regular languages is regular) and infinite.

And $\mathrm{B},\mathrm{C},\mathrm{D}\mathrm{holds}\mathrm{B}\subset \subset \mathrm{C}\subset \subset \mathrm{D}$true.