21. Post-Correspondence

Mar 22, 2022

We need a tool to prove some CFL problems are undecidable => the post correspondence (PC) problem.

The PC Problem

• input: two sets of $n$ strings: $A=w_1,w_2,\dots ,w_n$ and $B=v_1,v_2,\dots ,v_n$
• there is a post correspondence solution is there is a sequence $i,j,\dots ,k$ such that $w_i,w_j\dots w_k=v_i,v_j\dots v_k$ (indices may be repeated or omitted)

examples

     w1   w2    w3           v1   v2    v3
A : 100   11    111     B:  001  111    11

PC-solution I: 2,1,3    w2w1w3 = v2v1v3  => 11100111
PC-solution II: 2,3     w2w3   = v2v3    => 11111

     w1   w2    w3           v1   v2    v3
A :  00   001   1000     B:  0    11    011

This example has no solution, because strings from B 
is smaller than total length of strings from A.

Modified PC Problem

• input: two sets of $n$ strings: $A=w_1,w_2,\dots ,w_n$ and $B=v_1,v_2,\dots ,v_n$
• MPC solution: $1,i,j,\dots ,k$ => $w_1,w_i,w_j\dots w_k=v_1,v_i,v_j\dots v_k$

examples

     w1   w2    w3           v1   v2    v3
A :  11   111   100      B:  111  11    001

PC-solution:  1,3,2   w1w3w2 = v1v3v2  => 11100111

We can show:

1. MPC problem is undecidable by reducing the membership problem to MCP.
2. The PC problem is undecidable by reducing MPC to PC.

MPC is undecidable

Theorem: The MPC problem is undecidable.

Proof. We will reduce the membership problem to the MPC problem.

Membership problem:

• input is Turing machine $M$ and string $w$ => question $w\in L(M)$? => undecidable
• change it to: input unrestricted grammar $G$ (equivalent to TM) and string $w$ => question $w\in L(M)$? => undecidable

Suppose we have a decider for the MPC problem. Then:

string sequences $<A,B>$ => MPC problem decider => MPC solution (YES/NO)

We build a decider for the membership problem:

string sequences $<G,w>$ => MPC problem decider => $w\in L(G)$ (YES/NO)

Reduction of the membership problem to the MPC problem:

              Membership problem decider
        |===================================|
 G ---> | reduction |-----A----> | MPC      |---> yes 
 w ---> |           |-----B----> | decider  |---> no
        |===================================|

Show that reduction exists then problem is decidable => this is a contradiction.

Reduction: Convert grammar $G$ and string $w$ to sets of strings $A$ and $B$, such that $G$ generates $w$ $\iff$ there is a MPC solution for $A,B$.

How to build reduction:

• Left: how to build a, b
• Right: Grammar G productions
• a,b generate the derivation of $w$

$A$	$B$	Grammar $G$
$FS\Rightarrow$	$F$	$S$: start variable, $F$: special symbol
$a$	$a$	for every symbol $a$
$V$	$V$	for every variable $V$
$E$	$\Rightarrow wE$	string $w$, $E$: special symbol
$y$	$x$	For every production $x\to y$
$\Rightarrow$	$\Rightarrow$

example

• Grammar $G$:

  $S\to aABb$ | $Bbb$
  $Bb\to C$
  $AC\to aac$

• string $w=aaac$

$A$	$B$		$A$	$B$
$w_1:FS\Rightarrow$	$v_1:F$		$w_8:S$	$v_8:S$
$w_2:a$	$v_2:a$		$w_9:E$	$v_9$ : $\Rightarrow aaacE$
$w_3:b$	$v_3:b$		$w_{10}$ : $aABb$	$v_{10}$ : $S$
$w_4:c$	$v_4:c$		$w_{11}$ : $Bbb$	$v_{11}$ : $S$
$w_5:A$	$v_5:A$		$w_{12}$ : $C$	$v_{12}$ : $Bb$
$w_6:B$	$v_6:B$		$w_{13}$ : $aac$	$v_{13}$ : $AC$
$w_7:C$	$v_7:C$		$w_{14}$ : $\Rightarrow$	$v_{14}$ : $\Rightarrow$

$w=aaac\in L(G)$   $S\Rightarrow aABb\Rightarrow aAc\Rightarrow aaac$

Derivation: $s$

A:  |     w1     |    w10     |w14 |w2 |w5|w12 | w14 |w2 |  w13   | w9 | 
     F    S   =>   a   A  B b  =>   a    A  C    =>    a   a a c    E
B:  |v1| v10|v14 |v2 |v5 |v12 |v14 |v2 | v13   |        v9             |

It can be shown that $(A,B)$ has a MPC solution $\iff$ $w\in L(G)$.

              Membership problem decider
        |===================================|
 G ---> | construct |-----A----> | MPC      |---> yes 
 w ---> |   A,B     |-----B----> | decider  |---> no
        |===================================|

=> Since the membership problem is undecidable the MPC problem is undecidable.

PC is undecidable

Theorem: The PC problem is undecidable.

Proof. We will reduce the MPC problem to the PC problem.

Suppose we have a decider for the PC problem:

String sequences $<C,D>$ => PC problem decider => PC solution (YES/NO)

We build a decider for the MPC problem:

String sequences $<A,B>$ => MPC problem decider => MPC solution (YES/NO)

Reduction of the MPC problem to the PC problem:

                MPC problem decider
        |===================================|
 A ---> | reduction |-----C----> | PC       |---> yes 
 B ---> |           |-----D----> | decider  |---> no
        |===================================|

Translate $<A,B>$ input to the MPC problem to $<C,D>$ input to the PC problem:

• $A=w_1,w_2,\dots ,w_n$   $B=v_1,v_2,\dots ,v_n$

• $C=w_1^{{}^{\prime }},w_2^{{}^{\prime }},\dots ,w_n^{{}^{\prime }},w_{n+1}^{{}^{\prime }}$   $D=v_1^{{}^{\prime }},v_2^{{}^{\prime }},\dots ,v_n^{{}^{\prime }},v_{n+1}^{{}^{\prime }}$

• for each $i$ in A: $w_i={\sigma }_1{\sigma }_2\dots {\sigma }_k$ => replace in C: $w_i^{{}^{\prime }}={\sigma }_1^{\ast }{\sigma }_2^{\ast }\dots {\sigma }_k^{\ast }$

• for each $i$ in B: $w_i={\pi }_1{\pi }_2\dots {\pi }_k$ => replace in C: $v_i^{{}^{\prime }}=\ast {\pi }_1\ast {\pi }_2\ast \cdots \ast {\pi }_k$

• PC solution has to start with $w_1^{{}^{\prime }}$ and $v_1^{{}^{\prime }}$

  • PC solution C = D: $w_1^{{}^{\prime }},w_2^{{}^{\prime }},\dots ,w_n^{{}^{\prime }},w_{n+1}^{{}^{\prime }}=v_1^{{}^{\prime }},v_2^{{}^{\prime }},\dots ,v_n^{{}^{\prime }},v_{n+1}^{{}^{\prime }}$
  • MPC solution A = B: $w_1,w_2,\dots ,w_n=v_1,v_2,\dots ,v_n$

• => $<C,D>$ has a solution if and only if $<A,B>$ has a MPC solution

              MPC problem decider
        |===================================|
 A ---> | construct |-----C----> | PC       |---> yes 
 B ---> |   C,D     |-----D----> | decider  |---> no
        |===================================|

Since MPC problem is undecidable, the PC problem is undecidable.

CFL reductions

1. for context-free grammars $G_1$ and $G_2$, is $L(G_1)\cap L(G_2)=\mathrm{\varnothing }$
2. is context-free grammar $G$ ambiguous?

=> reduce PC problem to these problems to prove these are undecidable.

example 1: intersection problem

Suppose we have a decider for intersection problem:

$<G_1,G_2>$ => empty-intersection decider => YES/NO

We build a decider for PC problem: $<A,B>$ => PC decider => PC solution YES/NO

To reduce, we need to concert input instance $<A,B>$ to $<G_1,G_2>$.

Introduce new unique symbols: $a_1,a_2,\dots ,a_n$

• Grammar 1 (A):

  • $A=w_1,w_2,\dots ,w_n$
  • $L_A=\{s:s=w_i{w}_j\dots w_k{a}_k\dots a_j{a}_i\}$
  • CFG: $G_A:S_A\to w_i{S}_A{a}_i|w_i{a}_i$

• Grammar 2 (B):

  • $B=v_1,v_2,\dots ,v_n$
  • $L_B=\{s:s=v_i{v}_j\dots v_k{a}_k\dots a_j{a}_i\}$
  • CFG: $G_B:S_B\to v_i{S}_B{a}_i|v_i{a}_i$

If $(A,B)$ has a PC solution $\iff$ $L(G_1)\cap L(G_2)\ne \mathrm{\varnothing }$

• $L(G_1)\cap L(G_2)\ne \mathrm{\varnothing }$ => $s=w_i{w}_j\dots w_k{a}_k\dots a_j{a}_i$ and $s=v_i{v}_j\dots v_k{a}_k\dots a_j{a}_i$
• Because $a_1,a_2,\dots ,a_n$ are unique, there isa PC solution $w_i{w}_j\dots w_k=v_i{v}_j\dots v_k$

              PC problem decider
        |==================================|
 A ---> | construct |---G_A---> | Int.sec  |---> yes 
 B ---> |   CFGs    |---G_B---> | decider  |---> no
        |==================================|

Since PC problem is undecidable, the intersection problem is undecidable.

example 2: ambiguous grammar

For context-free grammar $G$ it is undecidable to determine if $G$ is ambiguous.

Proof. reduce PC problem to this problem.

              PC problem decider
        |==================================|
 A ---> | construct |    G      | ambig.   |---> yes 
 B ---> |   CFG     |---------> | decider  |---> no
        |==================================|

$S_A$ is start variable of $G_A$ and $S_B$ is start variable of $G_B$

=> $S$ is start variable of $G$   $S\to S_A|S_B$

If $(A,B)$ has a PC solution $\iff$ $L(G_1)\cap L(G_2)\ne \mathrm{\varnothing }$ $\iff$ $G$ is ambiguous.