PCP → CFG Ambiguity

PCP instance (dominoes)

Each domino i is a pair (t_i, b_i). The tool assigns a new terminal a_i used as an index marker in the grammar.

k = 0

Index prefix: –

Drop tiles here in order. You can reorder or delete individual tiles.

Wrap strings Sync with the index sequence input below.

PCP is undecidable. This solver performs a bounded search and may fail even if a solution exists.

Max depth:

Time limit (ms):

Node limit:

Use MPCP (force start with 1)

The grammar is constructed from your dominoes using the classical reduction PCP ⇒ AMB_CFG.

Index sequence (e.g., 1,3,2):

This builds two derivations: S⇒T⇒* and S⇒B⇒*. Matching outputs witness ambiguity.

Wrap strings

Tree T S ⇒ T ⇒* …

Tree B S ⇒ B ⇒* …

Reminder: this tool does not decide PCP or CFG ambiguity. It helps you explore the reduction and witness ambiguity when a solution is found.