پرش به محتوا

حل تمرین نظریه محاسبات/فصل اول/حل تمرین1-37

ویکی‎کتاب، کتابخانهٔ آزاد

حل تمرین1-37

تمرین[ویرایش]

Show that the language F={w|w is not a palindrome}satisfies the three conditions of the pumping lemma even though it is not regular.Explain why this fact does not contradict the pumping lemma!

نشان دهید که {قرینه نیست F={w|w اگرچه نامنظم است سه شرط لم تزریق را ارضا می کند. توضیح دهید چرا با لم تزریق تناقض ندارد.

  • این سوال غلط می باشد

می توان نشان داد که این زبان لم تزریق ندارد

ولی زبانهای دیگری وجود دارند که منظم نیستند ولی لم تزریق دارند

حل[ویرایش]

نشان می دهیم که لم تزریق ندارد.

لم تزریق را مورد بررسی قرار میدهیم:

با فرض عدد P (طول تزریق) داریم:

S=xyz , |S|>=P

S = ap!.b.ap!+p

=> y = ak , 1<k<p

xyyiz = ap+k .b.ap+1 لم تزریق دارد

i = 0 xz = ap-k.b.ap+1

داریم:

S = ap+ik.b.b.ap!+p | => y = ak , 1<k<p i = p! / k

عضو زبان نیست این تناقض است.

این زبان لم تزریق ندارد پس نامنظم است.