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

اگر B زبانی روی الفبای سیگما باشد نشان دهید که B=B+ اگر و تنها اگر BB زیرمجموعه B باشد.

حل:

برای اثبات این مسیله باید هر دو طرف قضیه را اثبات کنیم:

الف: اگر

آنگاه

اثبات: طبق تعریف می‌توان نوشت

و از آنجا که پس

قسمت B: اگر آنگاه

اثبات: برای آنکه نشان دهیم که ایتدا باید نشان دهیم که و سپس نشان دهیم که

طبق تعریف =>

اما برای آنکه نشان دهیم . برای اثبات این مورد از اثبات به روش استقرا کمک می گیریم:

استقرا)

اگر

و آنگاه زیرا

فرض استقرا)


حکم استقرا)