Question

lIhg derivation in tion for each of the following Post correspondence systems. 16, Find a solution for each la, aaa), taab, b), [abaa, ab la, abl. tba, aba), lb, aba), [bba, b] 17 Show that the following Post coespondence systems have no solutions a) [b, ba], [aa, bl, [bab, aa], [ab, ba] by [ab, al, [ba, bab], [b, aa], [ba, ab] c) [ab, aba], [baa, aa], [aba, baa] lab, bb], laa, ba), lab, abbl, [bb, bab] e) [abb, ab], [aba, ba], [aab, abab]

Answer 1

16.

B)[a,aaa ],[ aab,b],[abaa,ab]

i	xi	yi
1	a	aaa
2	aab	b
3	abaa	ab

here i am denoting the post correspondence with instance

x₁x₂x₃x1 = y₁y₂y₃y₁

aaababaaa = aaababaaa

hence it is a post correspondence system.

D)[a,ab],[ba,aba],[b,aba],[bba,b]

i	xi	yi
1	a	ab
2	ba	aba
3	ba	aba
4	bba	b

x₁x₂x₃x₁x₄x₃=y₁y₂y₁y₄y₃

ababaabbaba=ababaabbaba

hence it is a post correspondence system.

17)

B)[ab,a],[ba,bab],[b,aa],[ba,ab]

i	xi	yi
1	ab	a
2	ba	bab
3	b	aa
4	ba	ab

x₁x₂x₁x₃x_{4 not equal} y₁y₃y₁y₄y₂y₁

_{hence both terms are not equal. here y terms are not matching the x terms in the left side so.both are not equal}

_{It is not a Post correspondence system.}

_{D)[ab,bb],[aa,ba],[ab,abb],[bb,bab]}

i	xi	yi
1	ab	bb
2	aa	ba
3	ab	bbb
4	bb	bab

x₁x₂not equal because we cannot match the X2 in the y columns. so we cannot match them.

Hence it is not a post correspondence problem.