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:

MPC problem is undecidable by reducing the membership problem to MCP.
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\) \(\Leftrightarrow\) 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 \rightarrow y\)
\(\Rightarrow\)	\(\Rightarrow\)

example

Grammar \(G\):

\(S \rightarrow aABb\) | \(Bbb\)
\(Bb \rightarrow C\)
\(AC \rightarrow 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 \(\Leftrightarrow\) \(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^{'}, w_2^{'}, \dots, w_n^{'}, w_{n+1}^{'}\) \(D= v_1^{'}, v_2^{'},\dots, v_n^{'},v_{n+1}^{'}\)
for each \(i\) in A: \(w_i = \sigma_1\sigma_2\dots\sigma_k\) => replace in C: \(w_i^{'} = \sigma_1^{*}\sigma_2^{*}\dots\sigma_k^{*}\)
for each \(i\) in B: \(w_i = \pi_1\pi_2\dots\pi_k\) => replace in C: \(v_i^{'} = *\pi_1*\pi_2 * \dots * \pi_k\)
PC solution has to start with \(w_1^{'}\) and \(v_1^{'}\)
- PC solution C = D: \(w_1^{'}, w_2^{'}, \dots, w_n^{'}, w_{n+1}^{'} = v_1^{'}, v_2^{'},\dots, v_n^{'},v_{n+1}^{'}\)
- 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

for context-free grammars \(G_1\) and \(G_2\), is \(L(G_1) \cap L(G_2) = \emptyset\)
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_iw_j \dots w_ka_k\dots a_ja_i\}\)
- CFG: \(G_A: S_A \rightarrow w_iS_Aa_i | w_ia_i\)
Grammar 2 (B):
- \(B = v_1,v_2, \dots,v_n\)
- \(L_B = \{ s: s = v_iv_j \dots v_ka_k\dots a_ja_i\}\)
- CFG: \(G_B: S_B \rightarrow v_iS_Ba_i | v_ia_i\)

If \((A,B)\) has a PC solution \(\Leftrightarrow\) \(L(G_1) \cap L(G_2) \neq \emptyset\)

\(L(G_1) \cap L(G_2) \neq \emptyset\) => \(s = w_iw_j \dots w_ka_k\dots a_ja_i\) and \(s = v_iv_j \dots v_ka_k\dots a_ja_i\)
Because \(a_1, a_2, \dots, a_n\) are unique, there isa PC solution \(w_iw_j \dots w_k = v_iv_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 \rightarrow S_A | S_B\)

If \((A,B)\) has a PC solution \(\Leftrightarrow\) \(L(G_1) \cap L(G_2) \neq \emptyset\) \(\Leftrightarrow\) \(G\) is ambiguous.