حل تمرین نظریه زبانها و ماشینها/فصل دوم/حل تمرین بخش ۲-۴/حل تمرین ۱۰

پرسش :

پاسخ :

برهان خلف : فرض می کنیمQc و Qb ادغام پذیرند . پس چون Qb و Qa نیز ادغام پذیرند و ادغام پذیری رابطه هم ارزی دارد پس Qc و Qa ادغام پذیرند که تناقض است و حکم ثابت می شود .