patternMinor
Question about mapping reducibility
Viewed 0 times
reducibilitymappingquestionabout
Problem
I am working on an assignment where one of the sub questions is:
Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \Sigma^ \to \Sigma^$ such that for all $w \in \Sigma^*$, $w \in A$ iff $f(w) \in B$. Is it possible that $B$ is regular?
My take on this is that since context-free languages are on a 'higher' level than regular languages this is not possible. Apparently this is not the case, but I do not understand why.
Does anyone have a good explanation?
Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \Sigma^ \to \Sigma^$ such that for all $w \in \Sigma^*$, $w \in A$ iff $f(w) \in B$. Is it possible that $B$ is regular?
My take on this is that since context-free languages are on a 'higher' level than regular languages this is not possible. Apparently this is not the case, but I do not understand why.
Does anyone have a good explanation?
Solution
If $A$ is computable and $B$ is any nontrivial language (that is, $B \neq \emptyset,\Sigma^*$) then $A \leq_m B$. Indeed, pick $x \in B$ and $y \notin B$, and construct a computable reduction which decides whether its input is in $A$ or not, and outputs $x$ or $y$ accordingly.
Another issue you seem to be confused about is the meaning of context-free. The fact that a language is context-free doesn't preclude it from being regular. On the contrary, all regular languages are context-free.
Another issue you seem to be confused about is the meaning of context-free. The fact that a language is context-free doesn't preclude it from being regular. On the contrary, all regular languages are context-free.
Context
StackExchange Computer Science Q#96862, answer score: 4
Revisions (0)
No revisions yet.