Question

Let B and C be languages over $\sum =\left\{\mathbf{0},\mathbf{1}\right\}.$ Define

$\mathit{B}\mathbf{\neg }\mathit{C}\mathbf{=}\mathbf{\{}\mathit{w}\mathbf{^}\mathit{I}\mathit{B}\mathbf{|}\mathbf{ }\mathbf{ }\mathit{f}\mathit{o}\mathit{r}\mathbf{ }\mathit{s}\mathit{o}\mathit{m}\mathit{e}\mathbf{ }\mathit{y}\mathbf{^}\mathit{I}\mathit{C}\mathbf{,}\mathbf{ }\mathit{s}\mathit{t}\mathit{r}\mathit{i}\mathit{n}\mathit{g}\mathit{s}\mathbf{ }\mathit{w}\mathbf{ }\mathit{a}\mathit{n}\mathit{d}\mathbf{ }\mathit{y}\mathbf{ }\mathit{c}\mathit{o}\mathit{n}\mathit{t}\mathit{a}\mathit{i}\mathit{n}\mathbf{ }\mathit{e}\mathit{q}\mathit{u}\mathit{a}\mathit{l}\mathbf{ }\mathit{n}\mathit{u}\mathit{m}\mathit{b}\mathit{e}\mathit{r}\mathit{s}\mathbf{ }\mathit{o}\mathit{f}\mathbf{ }\mathbf{1}\mathit{s}\mathbf{\}}$

Show that the class of regular languages is closed under the$\stackrel{1}{\leftarrow }$operation.

Short answer

The class of regular languages closed under$B\leftarrow C$ operation.

Step-by-step solution

To explain regular languages

B and C are the two languages and

$B\leftarrow C=\{w\in B| for some y\in C, strings w and y contain equal numbers of 1s\}$over the alphabet.

So, it is given that B and C are regular languages

To Recognizes the language

Let$M_B$ be the DFA that recognizes the language B

$M_B=\left(Q_B,\sum ,{\delta }_B,q_B,F_B\right)$

Let $M_c$be the DFA that recognizes the language C

$M_C=\left(Q_C,\sum ,{\delta }_C,q_C,F_C\right)$

To construct an NFA which recognizes $B\leftarrow C$.

Construction of NFA to recognize $B\leftarrow C$.

Let$N=\left(Q,\sum ,\delta ,q,F\right)$ be the NFA.

Therefore, class of regular languages closed under$B\leftarrow C$ operation.