اگر B زبانی روی الفبای سیگما باشد نشان دهید که B=B+ اگر و تنها اگر BB زیرمجموعه B باشد.
حل:
برای اثبات این مسیله باید هر دو طرف قضیه را اثبات کنیم:
الف: اگر
آنگاه
اثبات: طبق تعریف میتوان نوشت
و از آنجا که پس
قسمت B: اگر آنگاه
اثبات: برای آنکه نشان دهیم که ایتدا باید نشان دهیم که و سپس نشان دهیم که
طبق تعریف =>
اما برای آنکه نشان دهیم . برای اثبات این مورد از اثبات به روش استقرا کمک می گیریم:
استقرا)
اگر
و آنگاه زیرا
فرض استقرا)
حکم استقرا)