Question

Let $\mathit{A}\mathbf{/}\mathit{B}\mathbf{=}\left\{\omega |\omega \chi A\mathrm{for}\mathrm{some}\chi \in B\right\}$.Show that if is regular and is any language, then$\mathit{A}\mathbf{/}\mathit{B}$ is regular.

Short answer

$A/B$is a regular language.

Step-by-step solution

To Regular recognize the language

Given language is$A/B=\left\{\mathrm{\omega }|\mathrm{\omega } \mathrm{\chi } \mathrm{A}\mathrm{for}\mathrm{some}\mathrm{\chi } \in \mathrm{B}\right\}$

Here, A is a regular language and B is any language.

Since A is a regular language, some DFA will be recognize the language A .

Let$M=(Q,\sum ,\delta ,q_{0}F)$be that which recognizes.

Here, Q is the set of states.

$\sum$is set of alphabets = of the alphabets for A and B.

$\delta$ is the transition function.

$q_0$is the start state.

F is the set of final states.

To Prove regular language and construct

To prove $A/B$ is a regular language, construct a DFA, that recognizes the language$A/B$

Let $M\text{'}=(Q\text{'},\sum \text{'},{\delta }_0^{\text{'}},F\text{'})$be the DFA, that recognizes $A/B$.

$Q\text{'}$= set of states =role="math" localid="1663154225010" $Q$

$\sum$=set of alphabets =$\sum$

$\delta \text{'}$= transition function =$\delta$

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

$F\text{'}=\{q\in Q|\exists \chi \in B$, such that M goes from q to some sate in F on reading $\chi$}

Thus, a DFA, $\mathrm{M}\text{'}$to recognize the language $A/B$ has been constructed.

Hence, $A/B$is a regular language.