FIT2014 Theory of Computation Lecture 21 Mapping Reductions
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 21
Mapping Reductions
slides by
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 18
Overview
I Mapping reductions: relating one language to another
I Definition
I Properties
I Examples
2 / 18
Mapping reductions
Definition
A mapping reduction from language K to language L is
a computable function f : Σ∗ → Σ∗ such that,
for every x ∈ Σ∗,
x ∈ K if and only if f (x) ∈ L.
Σ∗
K
Σ∗ \ K Σ∗
L
Σ∗ \ L
outputs of f
on Σ∗ \ K
outputs of f
on K
f
3 / 18
Mapping reductions
Notation:
K ≤m L means: ∃ a mapping reduction from K to L.
A very simple property:
Every language is mapping-reducible to itself:
∀L : L ≤m L
4 / 18
Mapping reductions
Theorem
If there is a mapping reduction f from K to L, then:
If L is decidable, then K is decidable.
Symbolically:
(K ≤m L) ∧ (L is decidable) =⇒ (K is decidable)
Proof.
Decider for K :
Input: x .
Compute f (x).
Run the Decider for L on f (x).
// This L-Decider accepts f (x) if and only if x ∈ K ,
since f is a mapping reduction from K to L.
Decidable
L
K
f
K
f
K
f
5 / 18
Mapping reductions
Corollary
If there is a mapping reduction f from K to L, then:
If K is undecidable, then L is undecidable.
Symbolically:
(K ≤m L)∧(K is undecidable) =⇒ (L is undecidable)
Proof.
Contrapositive of previous Theorem.
Decidable K
L
f
6 / 18
EQUAL to HALF-AND-HALF
Mapping reduction f :
Input: a word w over alphabet {a,b}
Sort w
Output the sorted word.
w ∈ EQUAL ⇐⇒ it has the same number of a’s as b’s
⇐⇒ after sorting, it has the same number of a’s as b’s
(since sorting does not affect letter frequencies)
⇐⇒ f (w) consists of some number of a’s followed by
the same number of b’s
⇐⇒ f (w) ∈ HALF-AND-HALF
7 / 18
HALF-AND-HALF to PARENTHESES
Mapping reduction:
Input: a word w
For each letter of w in turn:
If previous letter was b and current letter is a
// We have just seen ba which is impossible in HALF-AND-HALF.
Output the string ).
else
replace current letter as follows:
a 7→ (
b 7→ )
Output: the string obtained from w by doing all these replacements.
8 / 18
EQUAL to PARENTHESES
Is there a mapping reduction from EQUAL to PARENTHESES?
Yes! Compose the two previous mapping reductions.
This is a special case of:
Theorem.
Mapping reducibility is transitive:
K ≤m L ≤m M =⇒ K ≤m M.
9 / 18
Mapping reductions: transitivity
Theorem.
Mapping reducibility is transitive:
K ≤m L ≤m M =⇒ K ≤m M.
Proof.
Let f be a mapping reduction from K to L, and
let g be a mapping reduction from L to M.
We claim that the composition g ◦ f , defined for all w by g ◦ f (w) = g(f (w)),
is a mapping reduction from K to M.
Since f and g are both computable, g ◦ f must be too.
w ∈ K ⇐⇒ f (w) ∈ L (since f is a mapping reduction from K to L)
⇐⇒ g(f (w)) ∈ M (since g is a mapping reduction from L to M)
⇐⇒ (g ◦ f )(w) ∈ M (by definition of g ◦ f ).
10 / 18
FA-Empty −→ No-Digraph-Path
From previous lecture:
FA-Empty := {〈A〉 : A is a FA and L(A) = ∅}
Digraph-Path := {〈G , s, t〉 : G is a directed graph, s, t are vertices in G , and
there exists a directed s–t path in G .}
No-Digraph-Path := {〈G , s, t〉 : G is a directed graph, s, t are vertices in G , and
there does not exist a directed s–t path in G .}
We give a mapping reduction from FA-Empty to No-Digraph-Path.
11 / 18
FA-Empty −→ No-Digraph-Path
Mapping reduction
Input: 〈A〉 where A is a Finite Automaton.
1. Construct the directed graph G of A:
I initially, vertices of G := states of A
I every transition v
x−→ w in A becomes a directed edge (v ,w) from v to w in G .
I then add a new vertex t
I for every Final State v of A, add a new directed edge (v , t) from v to t in G .
2. Specify s and t:
I s := vertex of Start State of A.
I t is as created above (the new vertex).
3. Output: 〈G , s, t〉
12 / 18
FA-Empty −→ No-Digraph-Path
A ∈ FA-Empty ⇐⇒ there is no sequence of transitions in A leading
from Start State to a Final State
⇐⇒ there is no path in G leading from s to a vertex
representing a Final State
⇐⇒ there is no path in G leading from s to t
⇐⇒ 〈G , s, t〉 ∈ No-Digraph-Path
13 / 18
RegExpEquiv −→ FA-Empty
From previous lecture:
RegExpEquiv := {〈A,B〉 : A,B are regular expressions and L(A) = L(B)}
FA-Empty := {〈A〉 : A is a FA and L(A) = ∅}
We give a mapping reduction from RegExpEquiv to FA-Empty.
14 / 18
RegExpEquiv −→ FA-Empty
Mapping reduction:
Input: 〈A,B〉 where A and B are regular expressions
1. Construct a FA, C , that defines the language
(L(A) ∩ L(B)) ∪ (L(A) ∩ L(B)).
2. Output: C
15 / 18
Reducing from a decidable language
Let’s reduce from EnglishPalindromes to YearsOfTransitsOfVenus:
YearsOfTransitsOfVenus := {n : a Transit of Venus occurs in year n }
:= {. . . , 1761, 1769, 1874, 1882, 2004, 2012, 2117, . . .}
Mapping reduction:
Input: a string w over the English alphabet
If w is a palindrome
output 2012
else
output 2021.
16 / 18
Reducing from a decidable language
Theorem.
If L1 is decidable and L2 is any language except ∅ and Σ∗
then
L1 ≤m L2 .
Proof. Let D be a decider for L1.
Let x (yes) be any specific word in L2.
Let x (no) be any specific word in L2.
Mapping reduction from L1 to L2:
Input: a string w
1. Run D on w .
2. If D accepts w then output x (yes)
else output x (no).
There’s not much point
in a mapping reduction
that decides L1 !
17 / 18
Revision
Reading: Sipser, pp. 234–238.
18 / 18