حل تمرین نظریه محاسبات/فصل دوم/حل تمرین ۲-۱۸
(تغییرمسیر از حل تمرین نظریه محاسبات/فصل دوم/حل تمرین۲-۱۸)
الف) رشته ی سوال را به صورت 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های بزرگتر از صفر جمله ی ایجاد شده عضو زبان نیست که این مخالف فرض مستقل از متن بودن است.