Question

If $\mathit{A}{\mathbf{⩽}}_{\mathbf{m}}\mathit{B}$ and B is a regular language, does that imply that A is a regular language? Why or why not?

Short answer

If $A{⩽}_{m}B$ and B is a regular language, then that doesn’t implies that A is also regular language.

Step-by-step solution

Regular Language

Regular language is a language which can be accept by finite automata including deterministic and non-deterministic automata.

To check regularity of A

The statement, “If $A{⩽}_{m}B$and B is a regular language, does that imply that A is a regular language?” - is wrong. This is because the power of reduction function can be more the Deterministic Finite Automata (DFA).

For example, assume that there are two languages $A=\left\{0^n{1}^n\right|\text{for}n\ge 0\}$and $B=\left\{1\right\}$, both are over the function $\sum =\left\{0,1\right\}$.

Let there be a function as:

$\text{f}\left(\text{w}\right)=\{\begin{array}{c}1;ifw\in A\\ 0;ifw\notin A\end{array}$

Now we can see, that A is Context Free language, thus it must be decidable. So, this makes f as computable function.

We also observe that $w\in A$if and only if $f\left(w\right)=1$, this is only true if $f\left(w\right)\in B$.

Therefore, $A{⩽}_{m}B$ is regular language true but A is not regular language.