Question

If a ≤m b and b is regular, does that imply that a is a regular language? why or why not?

Answer 1

Answer: No. For example, define the languages A = { 0 n1 n | n ≥ 0 } and B = {1}, both over the alphabet Σ = {0, 1}. Define the function f : Σ∗ → Σ∗ as