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

حل

ادعا میکنیم p=4 است.

چون رشته هایی که بوسیله متغیر U تولید شده اند با کمترین طول به صورت 00#0 هستند حداقل مقدار P برابر 4 است همچنین اگر رشته با طول 4 بوسیله T تولید شده باشد ترکیبی از دو 0 و دو # است، که اگر v و y در لم تزریق را برابر 0 بگیریم لم برقرار است.

و اگر رشته با طول 4 بوسیله U تولید شده باشد ترکیبی از سه 0 و یک # است، که اگر v و y در لم تزریق را برابر 0 بگیریم باز لم برقرار است.

حال اگر فرض کنیم p=3 باشد و رشته ای مانند 0## که عضو زبان است را درنظر بگیریم به ناچار v یا y مساوی # میشود و با به توان رسیدن # رشته جدید دیگر عضو زبان نیست، پس p!=3 است.

پس حداقل طول تزریق برابر 4 است.