حل تمرین نظریه محاسبات/فصل دوم/حل تمرین ۲-۱۸

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

الف) رشته ی سوال را به صورت uvxyz در نظر بگیرید و فرض می‌کنیم که مستقل از متن باشد به طوریکه :

u = 0n1
v = 1n-1
x = 0
y = 0n-1
z = λ

که

|vxy| <= p

و p طول تزریق است.

می‌بینیم که برای عبارت uv ixy iz به ازای i‌های بزرگتر از صفر جمله ی ایجاد شده عضو زبان نیست که این مخالف فرض مستقل از متن بودن است.

ب) رشته ی سوال را به صورت uvxyz در نظر می‌گیریم و فرض می‌کنیم که مستقل از متن باشد به طوریکه :

u = 0n#
v = 02n
x = #
y = 02n
z = 0n

که

|vxy| <= p

و p طول تزریق است.

می‌بینیم که برای عبارت uv ixy iz به ازای i=2n و i‌های بزرگتر از صفر جمله ی ایجاد شده عضو زبان نیست که این مخالف فرض مستقل از متن بودن است.

منابع[ویرایش]

Pumping Lemma for context-free languages