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

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

u = 0ⁿ1
v = 1^n-1
x = 0
y = 0^n-1
z = λ

که

|vxy| <= p

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

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

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

u = 0ⁿ#
v = 0²ⁿ
x = #
y = 0²ⁿ
z = 0ⁿ

که

|vxy| <= p

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

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

منابع

Pumping Lemma for context-free languages