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

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

حل:

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

الف: اگر

$B=B^{+}$

آنگاه $BB\in B$

اثبات: طبق تعریف $B^{+}$ می‌توان نوشت $BB\in B^{+}$

و از آنجا که $B^{-}=B^{+}$ پس $BB\in B^{+}$

قسمت B: اگر $BB\in B^{+}$ آنگاه $B=B^{+}$

اثبات: برای آنکه نشان دهیم که $B=B^{+}$ ایتدا باید نشان دهیم که $BB\in B^{+}$ و سپس نشان دهیم که $B^{+}\in B$

طبق تعریف $B^{+}$ =>

$B\in B^{+}$

اما برای آنکه نشان دهیم $B^{+}\in B$. برای اثبات این مورد از اثبات به روش استقرا کمک می گیریم:

استقرا)

اگر

$W_{1}$ و $W_{2}$ آنگاه $W_{1}.W_{2}\in B$ زیرا $BB\in B$

فرض استقرا)

حکم استقرا)