PCP A- Describe post’s correspondence problem. B- Is post’s correspondence probl

Question

PCP A- Describe post’s correspondence problem. B- Is post’s correspondence problem solvable? Explain. C- Given the following: A = ( a , abaaa , ab ) and B = ( aaa , ab , b ) As two strings, provide a solution to PCP. PCP A- Describe post’s correspondence problem. B- Is post’s correspondence problem solvable? Explain. C- Given the following: A = ( a , abaaa , ab ) and B = ( aaa , ab , b ) As two strings, provide a solution to PCP. PCP A- Describe post’s correspondence problem. B- Is post’s correspondence problem solvable? Explain. C- Given the following: A = ( a , abaaa , ab ) and B = ( aaa , ab , b ) As two strings, provide a solution to PCP.

Explanation / Answer

A) post’s correspondence problem:

It is an undecidable decision problem.PCP is a NP- complete.

In PCP, ->consists of two lists of strings of alphabets.

Example:

A=a1,a2,a3,...an;

B=b1,b2,b3,..bn;

for n>0;

B)The instance of PCP has a solution, if the sequence of A and B are in equal length and yields,

same string.

C)

solution:

A=(a,abaaa,ab) B=(aaa, ab,b)

x1 x2 x3

A a abaaa ab

B aaa ab b

Here,

length of A= 8

length of B = 6

|x2x1x3| ? |y2y1y3| , length is not same.

SO, this Post Correspondence problem is undecidable

//for any calrification, please do comments

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.