Question

Find a match in the following instance of the Post Correspondence Problem.$\mathbf{\{}\mathbf{\left[}\frac{\mathbf{a}\mathbf{b}}{\mathbf{a}\mathbf{b}\mathbf{a}\mathbf{b}}\mathbf{\right]}\mathbf{,}\mathbf{}\mathbf{\left[}\frac{\mathbf{b}}{\mathbf{a}}\mathbf{\right]}\mathbf{,}\mathbf{}\mathbf{\left[}\frac{\mathbf{a}\mathbf{b}\mathbf{a}}{\mathbf{b}}\mathbf{\right]}\mathbf{,}\mathbf{}\mathbf{\left[}\frac{\mathbf{a}\mathbf{a}}{\mathbf{a}}\mathbf{\right]}\mathbf{\}}$

Short answer

The required match is$\left[aaaabab\right]$

Step-by-step solution

Post Corresponding Problem

Post Corresponding Problem is undecidable problem where we have more than one tile which contains multiple strings. The goal of this problem is to arrange the order of strings such that the numerator and denominator are identical.

Finding match

It is required to find the matching strings of Post Correspondence Problem in such a way that we will concatenate the strings in manner so that upper string and lower string are equal.

Let’s give number to each instance such as:

$1=\left[\frac{\text{ab}}{\text{abab}}\right]$, $2=\left[\frac{\text{b}}{\text{a}}\right]$, $3=\left[\frac{\text{aba}}{\text{b}}\right]$, $4=\left[\frac{\text{aa}}{\text{a}}\right]$

So, pattern is:$4,4,2,1$

We have,$\left[4,4,2,1\right]=\left[\frac{\left(\text{aa}\right)\left(\text{aa}\right)\left(\text{b}\right)\left(\text{ab}\right)}{\left(\text{a}\right)\left(\text{a}\right)\left(\text{a}\right)\left(\text{abab}\right)}\right]=\left[\frac{\text{aaaabab}}{\text{aaaabab}}\right]$

Hence this is the required match.